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;
}