Problemă de concurs certificată de InfoAs: Soluțiile tale trimise la această problemă sunt evaluate în exact același mediu ca și la concurs.
OJI 2020, clasele XI-XII · Clasa a XI-aGrafuriProbleme cu grafuri neorientate
Problema Ateleport
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ță
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 ieșire
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.0000 ≤ L, K ≤ 101 < Ti, P ≤ 100.0001 < Xi, Yi ≤ N- între oricare două planete există cel mult un canal
- pentru teste în valoare de aproximativ 25 de puncte se garantează că
K = 0și toate canalele de comunicare auTi = 1 - pentru alte teste în valoare de 25 de puncte se garantează că
K = 0 - pentru alte teste în valoare de 25 de puncte se garantează că
N ≤ 300 - se garantează că pentru toate testele există soluție
Exemple
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
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
Explicația exemplelor
Pentru primul exemplu: 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.
Pentru al doilea exemplu: 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.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;