Weighted shortest path (5) P68936
Write a program that, given a directed graph with postive and/or negative costs at the arcs (but no negative cycles), and two vertices x and y, computes the minimum cost to go from x to y.
Input
Input consists of several cases. Every case begins with the number of vertices n and the number of arcs m. Follow m triples u, v, c, indicating that there is an arc u → v of cost c, where u ≠ v, −1000 ≤ c ≤ 1000 and c≠ 0. Finally, we have x and y. Assume 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, and that for every pair of vertices u and v there is at most one arc of the kind u → v. All numbers are integers. Vertices are numbered from 0 to n−1. The directed graph has no negative cycles.
Output
For every case, print the minimum cost to go from x to y, if this is possible. If there is no path from x to y, state so.
Input
6 10
1 0 6
1 5 15
3 4 3
3 1 8
4 0 20
0 5 5
0 2 1
5 1 10
4 1 2
2 3 4
3 5
2 1
0 1 1000
1 0
8 11
0 1 10
0 7 8
1 5 2
2 1 1
2 3 1
3 4 3
4 5 -1
5 2 -2
6 5 -1
6 1 -4
7 6 1
0 1
Output
16 no path from 1 to 0 5
- Author
- Jordi Petit
- Language
- English
- Official solutions
- C++ Python
- User solutions
- C++ Python