Weighted shortest path (5) P68936


Statement
 

pdf   zip

thehtml

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 uv of cost c, where uv, −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 uv. 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.

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
    
    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
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python