Quant costa el camí de cost mínim? U74073


Statement
 

pdf   zip

thehtml

Escriviu un programa que, donat un graf dirigit amb costos positius a les arestes, i dos vèrtexs x i y, calculi el cost mínim per anar de x a y.

Entrada

L’entrada consta de diversos casos.

Cada cas comença amb el nombre de vèrtexs n i el nombre d’arestes m.

Segueixen m triplets u, v, c, que indiquen que hi ha una aresta u → v de cost c, on u ≠ v.

Finalment, tenim x i y.

Suposem que per a cada parell de vèrtexs u i v hi ha com a màxim una aresta del tipus u → v.

Tots els nombres són enters. Els vèrtexs es numeren de 0 a n−1.

Sortida

Per a cada cas, escriviu el cost mínim per anar de x a y, si això és possible. Si no hi ha cap camí de x a y, indiqueu-ho.

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

    16
no es pot anar de 1 a 0
100
    • Information
    Author
    Jordi Delgado (basat en el problema P43859 de Salvador Roura)
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python