Dijkstra? P26855


Statement
 

pdf   zip

html

Write a program that, given a directed multigraph with arcs with positive costs, computes the cost of the second cheapest walk from vertex 0 to every other vertex. Remember that a multigraph may have arcs from x to x, and more than one arc from x to y. Also remember that a walk can repeat vertices and arcs.

Input

Input consists of several cases. Every case begins with the number of vertices n and the number of arcs m, followed by m triples x y c to indicate an arc from x to y with cost c. Assume 2 ≤ n ≤ 104, 0 ≤ m ≤ 5n, that vertices are numbered from 0 to n − 1, and that every cost c is an integer number between 1 and 104.

Output

For every case, print the second minimum cost of walking from 0 to the rest of vertices, ordered from 1 to n − 1. If there is no second best walk to some vertex, just print “no”. Print a line with ten dashes at the end of every case.

Public test cases
  • Input

    4 3
    0 1 100
    0 3 200
    1 3 50
    
    5 8
    0 4 42
    0 4 12
    1 0 10000
    0 1 7
    0 3 100
    3 3 5000
    3 2 23
    0 2 6000
    

    Output

    no
    no
    200
    ----------
    10014
    5123
    5100
    42
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Dotzè Concurs de Programació de la UPC - Final
    Date
    2014-10-01