Se da un graf orientat cu n noduri si m muchii ponderate (costuri pozitive), doua noduri a si b, si un numar k. Determinati costul minim al unui drum de la a la b care foloseste cel mult k muchii.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza m linii, fiecare cu trei numere x y c, reprezentand o muchie orientata de la x catre y cu costul c. Urmeaza o linie cu a, b si k.
- Date de iesire
- Se afiseaza costul minim al unui drum de la a la b cu cel mult k muchii, sau -1 daca nu exista.
- Restrictii
- 1 <= n <= 200, 0 <= m <= 500, 0 <= k <= 50, 1 <= c <= 10^6
Exemple
Exemplul 1
Intrare
4 4 1 2 100 2 3 100 3 4 100 1 4 500 1 4 2
Iesire
500
Exemplul 2
Intrare
4 4 1 2 100 2 3 100 3 4 100 1 4 500 1 4 3
Iesire
300