Enunț
Pe insulele din golful Arin, fiecare pod se poate traversa în ambele sensuri. Traversarea durează un anumit număr de minute și costă un anumit număr de jetoane. Un curier pleacă de pe insula 1 spre insula n, cu B jetoane. Mai primește un permis care anulează taxa unei singure traversări. Permisul nu reduce timpul și poate rămâne nefolosit.
Cerință
Pentru fiecare expediție independentă, determină timpul minim în care curierul poate ajunge pe insula n fără să cheltuiască mai mult de B jetoane. Poate alege pe ce traversare folosește permisul. Dacă destinația este inaccesibilă în aceste condiții, răspunsul este -1.
Date de intrare
Prima linie conține T, numărul expedițiilor. Pentru fiecare expediție se citesc n, m și B, apoi m linii u v t c. Linia descrie un pod între insulele u și v: traversarea durează t minute și costă c jetoane. Rețeaua, banii și permisul se resetează la fiecare expediție.
Date de ieșire
Pentru fiecare expediție, pe o linie separată, afișează timpul minim sau -1. Dacă n=1, curierul este deja la destinație și timpul este 0.
Restricții
1 ≤ T ≤ 12; 1 ≤ n ≤ 150; 0 ≤ m ≤ 700; 0 ≤ B ≤ 30; 1 ≤ u,v ≤ n; u ≠ v; 1 ≤ t ≤ 10^9; 0 ≤ c ≤ 30. Nu există două poduri între aceeași pereche de insule. Suma valorilor m dintr-un fișier este cel mult 700, iar suma valorilor n este cel mult 450. Cheltuiala totală poate fi exact B. Timpul minim poate depăși limita unui întreg pe 32 de biți. Pentru 20% din punctaj, n ≤ 8 și m ≤ 10. Pentru alte 20%, toate taxele sunt 0. Pentru alte 20%, B=0. Pentru alte 20%, n ≤ 30. Ultimele 20% nu au restricții suplimentare.
Explicație
În prima expediție din exemplul 1, curierul alege 1 → 2 → 4. Folosește permisul pe primul pod, plătește 3 jetoane pe al doilea și ajunge în 4 minute. Fără permis, acest traseu ar costa 7 jetoane. Traseul 1 → 3 → 4 este accesibil și fără permis, dar durează 9 minute. În a doua expediție, sunt necesare două traversări cu taxă pozitivă; un singur permis și zero jetoane nu sunt suficiente.
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. Podurile se pot traversa în ambele sensuri. Prima valoare este timpul, a doua este taxa.Mărește schema ↗Date de intrare
2
4 4 3
1 2 2 4
2 4 2 3
1 3 1 1
3 4 8 0
3 2 0
1 2 1 1
2 3 1 1
Date de ieșire
4
-1
Exemplul 2
Date de intrare
1
2 1 0
1 2 1000000000 30
Date de ieșire
1000000000
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 →