Enunț
În portul Arin, un curier pleacă din depozitul 1 spre cheiul n. Străzile sunt cu sens unic, iar traversarea fiecăreia are un cost pozitiv. Primăria vrea să marcheze toate străzile care pot fi folosite de un curier fără să mărească prețul minim al călătoriei. Pot exista mai multe trasee la fel de ieftine.
Cerință
Determină câte arce distincte apar pe cel puțin un drum de cost minim de la 1 la n. Un arc folosit de mai multe drumuri minime se numără o singură dată. Dacă nu există niciun drum de la 1 la n, răspunsul este 0.
Date de intrare
Se citesc n și m, apoi m linii cu câte trei numere u v cost. Fiecare linie descrie arcul orientat de la u la v și costul traversării sale. Costul unui drum este suma costurilor arcelor sale.
Date de ieșire
Afișează un singur număr întreg: numărul arcelor care îndeplinesc cerința.
Restricții
1 ≤ n ≤ 30; 0 ≤ m ≤ n(n-1); 1 ≤ u,v ≤ n; u ≠ v; 1 ≤ cost ≤ 100. Nu există arce repetate. Pentru n=1, drumul minim este vid și răspunsul este 0.
Explicație
În primul exemplu, traseul 1 → 2 → 3 → 4 costă 3+2+1=6. Traseul 1 → 3 → 4 costă 10, deci nu este minim. Cele trei arce ale primului traseu sunt exact cele care se numără. În al doilea exemplu, curierul este deja la destinație și nu traversează niciun arc.
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. 4 vârfuri și 5 arce orientate.Mărește schema ↗Date de intrare
4 5
1 2 3
2 3 2
1 3 9
3 1 4
3 4 1
Date de ieșire
3
Exemplul 2
Date de intrare
1 0
Date de ieșire
0
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →