| Fişierul intrare/ieşire: | tempest.in, tempest.out | Sursă | ONIS 2015, Runda 2 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Daniel Constantin Anghel •Magnvs |
| Timp execuţie pe test | 2 sec | Limită de memorie | 66432 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
Tempest
Fie un graf cu N noduri si M muchii bidirectionale. Pentru fiecare muchie se cunoaste timpui necesar pentru a parcurge muchia respectiva. Yoshino se afla in nodul S(sursa) si parcurge un drum DAT pana in D(destinatie). Hakaze stie ca Yoshino cand o sa ajunga in nodul D, secunda imediat urmatoare acesta o sa moara. Ca urmare Hakaze trebuie sa il gaseasca pe Yoshino inainte ca acesta sa ajunga in destinatie (sau sa se intalneasca fix in destinatie). Hakaze este curioasa din cate noduri poate pleca astfel incat sa se poata intalni cu Yoshino inainte ca acesta sa moara (cei doi se pot intalni ori intr-un nod, ori pe o muchie).
Date de intrare
Fişierul de intrare tempest.in va contine pe prima linie un numar T, numarul de teste. Pentru fiecare test o sa avem: pe prima linie avem N, M, S si D. Pe urmatoarele M linii se vor afla cate 3 numere x y time, reprezentand ca exista muchie bidirectionala de la x la y care este parcursa in time unitati de timp. Urmatoarea linie contine un numar K (numarul de muchii parcurse de Yoshino). Pe ultima linie vor fi K numere, indicii muchiilor.
Date de ieşire
Fişierul de ieşire tempest.out va contine pentru fiecare din cele T teste cate 2 linii. Pe prima linie R, numarul de noduri din care poate sa plece Hakaze. Pe cea de a doua linie indicii celor R noduri.
Restricţii
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 300.000
- Costurile muchiilor vor fi in intervalul [1, 1.000.000.000]
- Cele K noduri trebuie afisate in ordine crescatoare
Exemplu
| tempest.in | tempest.out |
|---|---|
| 1 5 8 1 2 1 2 5 2 3 3 1 3 4 1 4 1 4 5 2 1 5 6 2 5 10 3 5 7 2 3 2 | 4 1 2 3 4 |
