Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DIJKSTRA - Dijkstra

Policz najkrótszą ścieżkę między podanymi wierzchołkami w danym grafie.
Wskazówka: Użyj algorytmu Dijkstry.
Wskazówka 2: set i cin/cout wystarczą wydajnościowo (sync_with_stdio(0)).

Wejście

pierwszy wiersz - liczba testów
Dla każdego testu podane są liczby V, K (liczba wierzchołków, liczba krawędzi),
a następnie w K wierszach podane są trójki liczb:
ai, bi, ci
Określają one, że graf zawiera krawędź skierowaną z ai do bi,
której waga to ci.
Pod tymi linijkami znajduje się para liczb A i B.
A to wierzchołek startowy, B - końcowy.
Liczby na wejściu są z zakresu 0..10000.

Wyjście

Należy podać dla każdego testu (w osobnych wierszach) liczbę C - długość najkrótszej ścieżki z wierzchołka A do B. Jeżeli w grafie nie istnieje ścieżka z A do B, dla tego testu program powinien wypisać słowo NIE

Przykład

Input:
3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3

Output:
12
5
NIE

Dodane przez:Robert Rychcicki
Data dodania:2008-11-21
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:ASM64 GAWK C++ 4.3.2 CPP CPP14 CLOJURE FSHARP GO NODEJS PDF PERL6 PS PYPY PYTHON3 PY_NBC SCALA SED TCL TEXT

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.