G - Road Blocked 2 Editorial by en_translator
Consider it as a problem on the graph \(G=(V,E)\), where the cities are the vertices and the roads are the edges.
Let \(E'\) be the subset of \(E\) consisting of the edges used in any shortest path from vertex \(1\) to vertex \(N\).
Then \(e=\{u,v\}\) is in \(E'\) if and only if either:
- (shortest distance from \(1\) to \(u\)) + (cost of edge \(\{u,v\}\)) + (shortest distance from \(v\) to \(N\)) = (shortest distance from \(1\) to \(N\)); or
- (shortest distance from \(1\) to \(v\)) + (cost of edge \(\{u,v\}\)) + (shortest distance from \(u\) to \(N\)) = (shortest distance from \(1\) to \(N\)).
By performing Dijkstra’s algorithm starting with vertices \(1\) and \(N\) to find the shortest distance from them to each vertex, one can obtain \(E'\) in a total of \(O(M\log N)\) time.
The answer is obviously No for any edge not in \(E'\). What about those in \(E'\)?
Let \(d_i\) be the shortest distance from vertex \(1\) to \(i\) in \(G\), and \(G'=(V,E')\).
Take an arbitrary permutation \(P\) of \((1,\ldots,N)\) so that \(i<j \implies d_{P_i} \leq d_{P_j}\). Then, the answer is Yes if only if there is a \(K\) such that \(e\) is the only edge connecting between two vertex sets \(S=\{P_1,\ldots,P_k\}\) and \(T=\{P_{k+1},\ldots,P_N\}\).
Intuitively, this is equivalent to the following: one can arrange the vertices of \(G'\) from nearest to furthest from vertex \(1\), and split it at a position into two sets of vertices, so that only \(e\) strides over the two parties.
Proof
Partition exists ⇒ answer is Yes
Without loss of generality, we may assume that $u\in S,v\in T$. By definition, $1=P_1\in S$; since $e\in E'$ we have $d_v\leq d_N$ thus $N\in T$. In $(V,E'\setminus\{e\})$, $S$ and $T$ form different connected components, so there is no path from vertex $1$ to vertex $N$ not containing $e$. By definition of $E'$, there is no shortest path from vertex $1$ to vertex $N$ on $G$ not containing $e$.No partition exists ⇒ answer is No
We have the following lemma.- For any shortest path from vertex $1$ to vertex $N$, the sequence of vertices in it forms a subsequence of $P$.
Proof of the lemma
It is obvious because of Pythagorean theorem and that $\{P_i,P_j\}\in E' \implies$ $d_{P_i}+(\text{the cost of edge } \{P_i,P_j\})=d_{P_j}$.Take \(k\) arbitrarily so that \(u\in S\) and \(v\in T\), swapping \(u\) and \(v\) if necessary (for example, one can take it so that \(P_k=u\)). By assumption, there is one more edge that strides over \(S\) and \(T\). Take one such edge, denoted by \(e'\). By definition of \(E'\), there is a shortest path from vertex \(1\) to vertex \(N\) containing \(e'\), so take one arbitrarily. By the lemma, this shortest path does not contain \(e\).
This problem can be solved fast using cumulative sums.
Example (for this case, the answer for all edge is No)：
The total complexity is \(O(M\log N)\).
Alternatively, one can use an algorithm to enumerate bridges, because the answer for an edge \(e\) in \(E'\) is Yes if and only if \(e\) is a bridge in \(G'\). (The necessary and sufficient condition introduced above is stronger than “\(e\) is a bridge in \(G\),” but actually it is sufficient to enumerate the bridges.)
posted:
last update: