| Fişierul intrare/ieşire: | northrend.in, northrend.out | Sursă | Infoarena Monthly 2014, Runda 8 |
| Autor | Teodor Plop | Adăugată de |  Cristian Lambru •maritim |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Hero's Call: Northrend!
"By order of his royal highness, King Varian Wrynn, all able-bodied citizens of the Alliance are to report to Recruitment Officer Blythe at Valiance Keep in Borean Tundra.
The Valiance Expedition needs your help to keep the forces of the Scourge under control and safeguard civilized lands! Make your way to the Stormwind Docks and take the ship north to Valiance Keep.
For the glory and honor of the Alliance!"
Rewards
You will receive: 50 - 100 points of experience (if completed within 2.5 hours)
Este timpul pentru unul dintre ultimii eroi din Azeroth, pe numele său Leeroy Jenkins, să răspundă chemării regelui Varian Wrynn, în lupta împotriva armatei condusă de către Lich King.
În Azeroth sunt N oraşe numerotate de la 1 la N, conectate între ele prin exact N - 1 portale "bidirecţionale". Portalul i îl va duce pe eroul nostru Leeroy din oraşul A[i] în oraşul B[i], dacă acesta plăteşte o taxă în valoare de C[i] monezi de argint, sau invers (din oraşul B[i] în A[i], pentru aceeaşi taxă). Se garantează că există o modalitate de a călători între oricare două oraşe.
După cum se poate observa, misiunea acestuia este să ajungă în oraşul Valiance Keep, numerotat cu X, pentru a vorbi cu Ofiţerul Blythe. Leeroy şi-ar dori să nu cheltuie foarte mult în drumul său către acest oraş, deoarece are nevoie de o cantitate destul de mare de monezi pentru a îşi cumpăra o armă nouă, mai puternică. De aceea, când pleacă dintr-un oraş, Leeroy are grijă ca la fiecare pas să acceseze cel mai ieftin portal (portalul având costul cel mai mic) care este conectat de oraşul în care se află şi care îl duce către un oraş nevizitat până în acel moment.
Ştiind că Leeroy are voie să plece din orice oraş diferit de Valiance Keep (oraşul X), afişaţi câte drumuri care îl duc pe Leeroy în Valiance Keep (oraşul X) există.
Date de intrare
Fişierul de intrare northrend.in conţine pe prima linie numerele naturale N X, separate între ele printr-un spaţiu. Pe fiecare linie i din următoarele N - 1, se vor găsi 3 numere naturale A[i] B[i] C[i], cu următoarea semnificaţie: există un portal care conectează oraşul A[i] de oraşul B[i], având costul C[i].
Date de ieşire
În fişierul de ieşire northrend.out se va găsi un singur număr natural, reprezentând numărul de drumuri care îl duc pe Leeroy în Valiance Keep (oraşul X).
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ X ≤ N
- 1 ≤ C ≤ 109
- Se garantează că nu există două portale având acelaşi cost.
Exemplu
| northrend.in | northrend.out |
|---|---|
| 4 4 1 2 2 2 3 1 2 4 3 | 0 |
| 5 3 1 2 1 2 3 2 3 4 3 2 5 4 | 2 |
Explicaţie
Pentru primul exemplu:
1. Dacă Leeroy pleacă din oraşul 1, el va parcurge oraşele 1 2 3, oprindu-se în oraşul 3.
2. Dacă Leeroy pleacă din oraşul 2, el va parcurge oraşele 2 3, oprindu-se în oraşul 3.
3. Dacă Leeroy pleacă din oraşul 3, el va parcurge oraşele 3 2 1, oprindu-se în oraşul 1.
Prin urmare, numărul de drumuri care îl duc pe acesta în oraşul 4 este 0 (zero).
Pentru cel de-al doilea exemplu:
Leeroy poate ajunge în oraşul 3 dacă pleacă din oraşul 1 sau din oraşul 4.
