Weighted shortest path (4) P39586


Statement
 

pdf   zip

thehtml

Write a program that, given a directed graph with positive costs at the arcs, and two vertices x and y, computes the minimum cost to go from x to y, and the number of ways of going from x to y with such minimum cost.

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.

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

Output

For every case, print the minimum cost to go from x to y, and the number of different paths that achieve this cost. This number will never exceed 109. 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 60
    0 2
    

    Output

    cost 16, 1 way(s)
    no path from 1 to 0
    cost 100, 2 way(s)
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python