Camí màxim P14985


Statement
 

pdf   zip

thehtml

Donat un graf dirigit sense cicles, on els arcs tenen costs (potser negatius), calculeu-ne el camí de cost màxim.

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters. Cada cas comença amb el nombre de vèrtexs n i el nombre d’arcs m, seguits d’m triplets x y c descrivint un arc des d’x fins a y de cost c, amb xy i | c | ≤ 104. Suposeu 1 ≤ n ≤ 105, 0 ≤ m ≤ 5n, que els vèrtexs es numeren a partir de 0, i que no hi ha més d’un arc d’x a y.

Sortida

Per a cada graf, escriviu el vèrtex inicial, el vèrtex final i el cost del camí de cost màxim. En cas d’empat, trieu el camí amb vèrtex inicial màxim. En cas d’un altre empat, trieu el camí amb vèrtex final màxim. Tingueu en compte que els camins buits tenen cost 0.

Public test cases
  • Input

    4 3
    1 0 10  2 3 15  0 2 -5
    3 1
    2 1 -10000
    4 4
    2 0 1000  2 1 1000  3 0 1000  3 1 1000
    

    Output

    1 3 20
    2 2 0
    3 1 1000
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++