Fişierul intrare/ieşire:tempest.in, tempest.outSursăONIS 2015, Runda 2
AutorEugenie Daniel PosdarascuAdăugată deMagnvsDaniel Constantin Anghel Magnvs
Timp execuţie pe test4 secLimită de memorie66432 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.intempest.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?