Carreteres curtes

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 $\ell_1, \dots, \ell_k$ , i $\ell = \max(\ell_1, \dots, \ell_k)$ , volem que $\ell$ 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$ $\ell$ , amb $x \ne y$ , indicant una carretera que va de $x$ a $y$ de longitud $\ell$ . Suposeu $2 \le n \le 10^4$ , $1 \le m \le 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 $10^5$ , 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 \to 4 \to 2 \to 1$ , el qual té una carretera (la $0 \to 4$ ) de longitud màxima 80.

Pista

Considereu una variant de l’algorisme de Dijkstra.

Informació del problema

Autoria: Salvador Roura

Generació: 2026-01-25T22:48:14.512Z