Elevi Pentru Elevi Arges - XI/XII | Zboruri

This was the problem page during the contest. Access the current page here.
Time limit: 0.15s Memory limit: 14MB Input: zboruri.in Output: zboruri.outPoints by default: 10p

Tocmai ați fost angajat la compania aeriană „Brătianu Airlines”. Știți că există NN orașe indexate de la 11 la NN între care compania organizează MM trasee de zbor. Se dă fiecare traseu de zbor prin numărul orașului din care decolează, orașul în care aterizează, durata și prețul zborului.
Din cauza unei supraîncărcări a rețelei, cauzată de aglomerația din aeroport, trebuie să găsiți manual o metodă de a găsi zboruri pentru pasageri.

Cerință

Pentru două orașe date, SS și FF, trebuie să aflați:

  1. Un drum[1]^{[1]} de la orașul SS la orașul FF care să aibă durată[2]^{[2]} minimă, dacă există.
  2. Dintre toate drumurile de durată minimă de la orașul SS la orașul FF, care este prețul[3]^{[3]} minim al unui astfel de drum, dacă există.

[1]^{[1]} Numim drum de la un oraș UU la un oraș VV un șir X1X_1, X2X_2, ..., XkX_k, unde X1=UX_1 = U și Xk=VX_k = V, iar pentru orice ii, cu 1i<K1 \le i < K, există un zbor de la XiX_i la Xi+1X_{i + 1}.

[2]^{[2]} Definim durata unui drum X1X_1, X2X_2, ..., XkX_k ca fiind suma duratelor zborurilor de la XiX_i la Xi+1X_{i + 1}, cu 1i<K1 \le i < K.

[3]^{[3]} Definim prețul unui drum X1X_1, X2X_2, ..., XkX_k ca fiind suma prețurilor zborurilor de la XiX_i la Xi+1X_{i + 1}, cu 1i<K1 \le i < K.

Date de intrare

Pe prima linie a fișierului de intrare zboruri.in se află cinci numere naturale nenule, în această ordine: CC, NN, MM, SS, respectiv FF, unde CC reprezintă numărul cerinței care se va rezolva, iar restul au semnificațiile din enunț.

Pe următoarele MM linii se află descrierile celor MM zboruri, câte un zbor pe linie. Al ii-lea zbor, cu 1iM1 \le i \le M, este dat prin patru numere naturale nenule, în această ordine:

  • UiU_i - orașul de decolare;
  • ViV_i - orașul de aterizare;
  • TiT_i - durata zborului;
  • PiP_i - prețul zborului.

Date de ieșire

Fișierul de ieșire zboruri.out va conține pe prima linie:

  • Pentru C=1C = 1, șirul X1X_1, X2X_2, ..., XkX_k, ce reprezintă un drum de durată minimă de la orașul SS la orașul FF, dacă există. Dacă nu există niciun astfel de drum se va afișa numărul 1-1.
  • Pentru C=2C = 2, un singur număr natural PminP_{min}, ce reprezintă prețul minim dintre prețurile tuturor drumurilor de durată minimă de la SS la FF, dacă există. Dacă nu există niciun astfel de drum se va afișa numărul 1-1.

Restricții și precizări

  • 2N21052 \le N \le 2 \cdot 10^5
  • 2Mmin(2105,N(N1))2 \le M \le \min(2 \cdot 10^5, N \cdot (N - 1))
  • 1Ui,ViN1 \le U_i, V_i \le N, cu 1iM1 \le i \le M
  • 1Ti,Pi1091 \le T_i, P_i \le 10^9, cu 1iM1 \le i \le M
  • Pentru prima cerință, dacă există mai multe drumuri de durată minimă, se va puncta oricare dintre acestea.
  • Se acordă 10 puncte din oficiu.
# Punctaj Restricții
1 30 C=1C = 1
2 20 C=2C = 2; Există un singur drum de durată minimă
3 40 Fără restricții suplimentare

Exemplul 1

zboruri.in

1 6 8 1 4
1 2 3 3
1 6 1 1
2 3 5 1
2 5 2 2
3 4 3 1
5 4 4 2
6 2 2 1
6 5 4 3

zboruri.out

1 2 5 4

Exemplul 2

zboruri.in

2 6 8 1 4
1 2 3 3
1 6 1 1
2 3 5 1
2 5 2 2
3 4 3 1
5 4 4 2
6 2 2 1
6 5 4 3

zboruri.out

6

Explicație

Zborurile din ambele exemple se pot reprezenta grafic ca în imaginea următoare:

Cercurile reprezintă orașele, cu indicele lor înăuntru, și săgețile reprezintă zborurile, unde este notată cu albastru durata zborului și cu roșu prețul zborului.

Pentru primul exemplu, durata minimă a unui zbor este 99, iar toate zborurile cu această durată sunt:

  • 11, 66, 55, 44;
  • 11, 66, 22, 55, 44;
  • 11, 22, 55, 44.

Oricare dintre acestea este considerat corect.

Pentru al doilea exemplu, drumurile de durată minimă de mai sus au prețurile:

  • 1+3+2=61 + 3 + 2 = 6;
  • 1+1+2+2=61 + 1 + 2 + 2 = 6;
  • 3+2+2=73 + 2 + 2 = 7.

Astfel prețul minim al unui drum de durată minimă este 66.

Log in or sign up to be able to send submissions!