| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
GML0567 - ПУТЬ |
Дан ориентированный граф, с N вершинами и M ребрами. В графе нету петель. Между двумя вершинами может быть более одной дуги. У Вас есть K запросов вида: “Какая длинна у кратчайшего пути от вершины U к вершине V. Если не существует пути выведите: -1”. Ответьте на все запросы.
Входные данные.
Первая строка содержит два числа: N, M (1<N≤100, 1<M≤10000).
Следующие M строк описывают граф: X Y Z (1 ≤ X, Y ≤ N, 0 < Z ≤ 100), есть дуга из вершины X в вершину Y, весом Z.
Следующая строка содержит одно число: K (0 < K ≤ 1 00 000).
Следующие K строк описывают запрос: U, V (0 < U, V ≤ N).
Выходные данные.
Выведите ответы на запросы.
Пример.
|
N |
stdin |
stdout |
|
1 |
4 6 1 2 6 3 1 3 3 2 2 2 3 1 2 4 3 1 2 7 4 4 3 3 4 2 1 2 3 |
-1 5 4 1 |
| Ավելացրեց. | Հրանտ Հովհաննիսյան |
| Ամսաթիվ. | 2016-08-29 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE |
| Աղբյուրը. | Գոմել: Ավագ տարիքային խումբ: |
RSS