Problem 51: K-th Shortest Path in a Graph

Problem Statement: Given a directed weighted graph, find the k-th shortest simple path from source to target. Paths are considered distinct if their sequences of nodes differ. If less than k paths exist, output -1.

Input

The first line contains four integers n, m, s, t, where n is the number of nodes, m the number of edges, s the source and t the target. The next m lines each contain three integers u, v, w representing an edge from u to v with weight w. The last line contains an integer k.

Output

Print the length of the k-th shortest simple path from s to t, or -1 if it does not exist.

Examples


Input:
4 5 1 4
1 2 1
2 4 2
1 3 2
3 4 2
2 3 1
2

Output:
4

Solution Explanation

This problem can be solved with a modification of Dijkstra's algorithm where each node maintains the best k distances found so far. A priority queue is used to iterate over the paths in increasing order of distance. When the target node has been popped k times, we output the current distance.

Solution in C++


#include 
#include 
#include 
#include 
using namespace std;

struct State {
    int node;
    long long dist;
    bool operator>(const State &other) const { return dist > other.dist; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s, t;
    cin >> n >> m >> s >> t;
    vector>> graph(n+1);
    for(int i = 0; i < m; i++){
        int u, v, w; 
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }
    int k; 
    cin >> k;

    const long long INF = 1e18;
    vector> dist(n+1, vector());
    priority_queue, greater> pq;
    pq.push({s, 0});

    while(!pq.empty()){
        State cur = pq.top();
        pq.pop();
        int u = cur.node;
        long long d = cur.dist;
        if(dist[u].size() >= k) continue;
        dist[u].push_back(d);
        if(u == t && dist[u].size() == k){
            cout << d << "\n";
            return 0;
        }
        for(auto &edge : graph[u]){
            int v = edge.first;
            int w = edge.second;
            if(dist[v].size() < k){
                pq.push({v, d + w});
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}