Weighted shortest path (2) P13994


Statement
 

pdf   zip

thehtml

Write a program that, given a directed graph with positive costs at the arcs, and two vertices x and y, prints the path of minimum cost that goes 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 uv of cost c, where uv and 1 ≤ c ≤ 104. 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 uv. All numbers are integers. Vertices are numbered from 0 to n−1. If y is reachable from x, you have the guarantee that there is a unique path.

The condition for c was previously c ≤ 1000. It was updated to create new test cases.

Output

For every case, print the path of minimum cost that goes from x to y. If there is no path from ‍x to y, state so.

Public test cases
  • 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
    
    3 3
    0 2 100
    0 1 40
    1 2 70
    0 2
    

    Output

    3 4 1 0 5
    no path from 1 to 0
    0 2
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python