Fișierul intrare/ieșire ateleport.in, ateleport.out Sursă OJI 2020, clasele 11-12
Autor Alexandru Turdean Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 1.5 sec Limită de memorie 32768 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Ateleport (clasele 11-12)

Marian se află în galaxia OJI-2020 și este anul 11235. În această galaxie există N planete diferite și M canale bidirecționale de transport de tipul (x, y, t) care îți permit să te deplasezi de pe planeta x pe planeta y (sau invers) în t secunde.

Dar Marian este un adevărat inginer și, pentru că i se pare foarte ineficientă această metodă de transport, a dezvoltat un dispozitiv care îți permite teleportarea de pe o planetă x pe orice altă planetă y în P secunde cu condiția că ai putea ajunge pornind de pe planeta x pe planeta y folosind maxim L canale de transport.

Acest dispozitiv este momentan doar un prototip, așa că nu îl poate folosi mai mult de K ori. Marian se află pe planeta 1 și te roagă să îi spui care e timpul minim necesar pentru a ajunge pe planeta N.

Cerința

Să se scrie un program care calculează timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.

Date de intrare

Fișierul de intrare ateleport.in conține pe prima linie 5 valori N, M, P, L, K, separate printr-un singur spațiu, cu semnificația din enunț.

Pe fiecare din următoarele M linii se vor afla câte 3 valori Xi, Yi, Ti care descriu un canal de transport.

Date de iesire

Fișierul de ieșire ateleport.out va conține o singură valoare pe prima linie care reprezintă
timpul minim necesar pentru a ajunge pe planeta N pornind de pe planeta 1.

Restricții și precizări

  • 1 < [$N], M ≤ 10 000$
  • 0 ≤ [$L], K ≤ 10$
  • 1 < $Ti, P ≤ 100 000$
  • 1 < $Xi, Yi ≤ N$
  • între oricare două planete există cel mult un canal;
  • pentru teste în valoare de 30 de puncte se garantează că K = 0 și toate canalele de comunicare au Ti = 1;
  • pentru ALTE teste în valoare de 20 de puncte se garantează că K = 0;
  • pentru ALTE teste în valoare de 20 de puncte se garantează că N300;
  • se garantează că pentru toate testele există soluție;
  • în concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemple

ateleport.in ateleport.out Explicație
6 7 3 2 1
1 2 2
1 3 5
2 3 4
2 4 23
3 4 6
5 4 7
5 6 9
14
Dispozitivul se poate folosi cel mult o dată. Pentru a ajunge pe planeta 6 în timp minim vom parcurge canalul 1 → 2 apoi ne vom teleporta până pe planeta 5 de unde vom mai
parcurge canalul 5 → 6. Costul final este 2 + 3(teleportare) + 9 = 14.
6 7 3 2 0
1 2 2
1 3 5
2 3 4
2 4 23
3 4 6
5 4 7
5 6 9
27
Dispozitivul nu se poate folosi deloc. Pentru a ajunge pe planeta 6 de pe planeta 1 în timp minim,
se vor parcurge canalele în ordinea 1→3→4→5→6 și se obține timpul 5+6+7+9=27 de secunde.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii