Two Kinds of Shortest-Path Queries¶
Estimated time limit: 1 seconds. Memory limit: 128 MB.
The actual time limit is twice the slowest-case median runtime of the reference solution on the target judge, rounded up to a multiple of \(0.5\) seconds. See the benchmark environment.
Story¶
A route service answers shortest-path queries between stations. Some networks are large but receive only one query. The remaining networks have few stations and may receive many queries.
(This story was rewritten by GPT-6.)
Formal Problem Statement¶
An undirected graph has \(n\) vertices numbered \(1,\ldots,n\) and \(m\) nonnegative weighted edges. Answer \(q\) queries in order. Each query specifies two vertices and asks for the minimum sum of edge weights along a path between them. Output \(-1\) if they are disconnected.
Every input satisfies \(q=1\) or \(n\le500\) . Parallel edges, self-loops, zero-weight edges, and repeated queries are allowed. A vertex can reach itself using no edges, so its distance to itself is zero.
Input Format¶
The first line contains \(n,m,q\) . Each of the next \(m\) lines contains \(u,v,c\) , describing an undirected edge of weight \(c\) between \(u,v\) . Each of the following \(q\) lines contains two vertices \(u,v\) for one query.
Output Format¶
Print \(q\) lines in query order. Each line contains the shortest-path weight, or \(-1\) if the queried vertices are disconnected.
Samples¶
Sample 1¶
Input¶
4 4 4
1 2 9
1 2 2
2 3 4
1 3 10
1 3
3 1
1 4
4 4
Output¶
6
6
-1
0
Sample 2¶
Input¶
4 3 1
1 2 1000000000
2 3 1000000000
3 4 1000000000
1 4
Output¶
3000000000
Sample Explanation¶
In the first sample, choose the weight-two edge between \(1,2\) , then the weight-four edge to \(3\) , for distance six. The reverse query also has distance six because the graph is undirected. Vertex \(4\) is disconnected from the others, but its distance to itself is zero.
The second sample has just one simple path between \(1,4\) , of total weight \(3000000000\) .
Constraints and Guarantees¶
For all inputs, \(1\le n,m,q\le5\times10^5\) , \(1\le u,v\le n\) , \(0\le c\le10^9\) , and \(q=1\) or \(n\le500\) . The graph need not be connected.
| Score share | Additional conditions |
|---|---|
| 30% | \(q=1\) |
| 40% | \(q=1\) and \(n\le500\) |
| 30% | \(n\le500\) |