410795: GYM104114 K Knowledge Testing Problem

Every respectable contest must have a textbook graph problem. No convoluted processes, no weird observations; just pure, raw algorithmics. Lucky for you, you've just found it!

The picture above depicts the example test case.

You are given an undirected, weighted graph with $$$n$$$ vertices and $$$m$$$ edges, as well as $$$q$$$ queries of form $$$(a_i, b_i)$$$. For each of the queries, find the length of the shortest path between vertices $$$a_i$$$ and $$$b_i$$$.

The input consists of $$$m + q + 1$$$ lines. The first line of the input will contain three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \leq n \leq 100\:000$$$, $$$1 \leq m \leq 200\:000$$$, $$$1 \leq q \leq 25\:000$$$). Each of the next $$$m$$$ lines contain three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$, denoting undirected edge between vertices $$$u_i$$$ and $$$v_i$$$ of length $$$w_i$$$ ($$$1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10^9$$$). Finally, each of the last $$$q$$$ lines contain two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$).

There is at most one edge between any pair of vertices, and no edges that connect a vertex with itself.

Moreover, it is guaranteed that all $$$m$$$ edges $$$u_i$$$, $$$v_i$$$ satisfy $$$|u_i - v_i| \leq 10$$$.

Output $$$q$$$ lines. The $$$i$$$-th line should contain a single positive integer, representing the minimum length of a path that connects the vertices in the $$$i$$$-th query. If there is no such path, output $$$-1$$$ for that specific query.

6 5 3
1 3 7
3 4 5
1 4 1
2 5 10
2 6 12
6 5
1 3
1 5

22
6
-1