Carreteres curtes X50299


Statement
 

pdf   zip

html

Considereu el mapa d’un país, amb n ciutats (numerades entre 0 i n−1) i m carreteres unidireccionals que les connecten. Cada carretera té una certa longitud. Volem anar de la ciutat 0 a la ciutat 1. Com que viatgem amb persones que es maregen, i no volem parar a estirar les cames a mitja carretera, volem seguir el camí tal que la carretera més llarga que faci servir sigui el més curta possible. És a dir, si el camí usa k carreteres, amb longituds ℓ1, …, ℓk, i ℓ = max(ℓ1, …, ℓk), volem que ℓ sigui tan petita com sigui possible.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguits d’m triplets x y ℓ, amb x ≠ y, indicant una carretera que va de x a y de longitud ℓ. Suposeu 2 ≤ n ≤ 104, 1 ≤ m ≤ 10n, que no hi ha més d’una carretera d’x a y en aquest mateix ordre, que les longituds es troben entre 1 i 105, i que sempre hi ha algun camí entre 0 i 1.

Sortida

Per a cada cas, escriviu la longitud màxima de les carreteres del millor camí possible.

La segona línia de l’exemple de sortida es correspon al camí 0 → 4 → 2 → 1, el qual té una carretera (la 0 → 4) de longitud màxima 80.

Pista

Considereu una variant de l’algorisme de Dijkstra.

Public test cases

  • Input

    2 2
0 1 100000
1 0 42

5 6
0 1 90
0 4 80
4 1 60
0 2 100
2 1 60
4 2 70

    Output

    100000
80
    • Information
    Author
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++