No.1301 Strange Graph Shortest Path
nok0
zkou
Kite_kumaProblem Statement
You are given a simple connected undirected graph with $N$ vertices and $M$ edges, where the vertices are numbered from $1$ to $N$ and the edges are numbered from $1$ to $M$.
Edge $i$ of this graph connects vertices $u_i$ and $v_i$ bidirectionally, and its length is $c_i$.
However, once edge $i$ has been traversed, the length of edge $i$ changes from $c_i$ to $d_i$. Here, it is guaranteed that $c_i \le d_i$.
The same edge can be traversed at most twice.
Find the length of the shortest path that starts at vertex $1$, passes through vertex $N$, and returns to vertex $1$.
Constraints
- All inputs are integers.
- The given graph is a simple connected undirected graph.
- $2 \le N\le 10^5$
- $N - 1 \le M\le \mathrm{min}\left(10^5, \frac{N (N - 1)} {2}\right)$
- $1 \le u_i < v_i\le N$
- $1 \le c_i \le d_i\le 10^{9}$
Input
$N\ M$ $u_1\ v_1\ c_1\ d_1$ $u_2\ v_2\ c_2\ d_2$ $\dots$ $u_M\ v_M\ c_M\ d_M$
Output
Output the length of the shortest path that starts at vertex $1$, passes through vertex $N$, and returns to vertex $1$.
Sample
Sample 1
Input
3 2 1 2 1 4 2 3 1 2
Output
8
To start at vertex $1$, pass through vertex $N = 3$, and return to vertex $1$, the only option is to move through the vertices as $1$ → $2$ → $3$ → $2$ → $1$. The length of the shortest path is $1 + 1 + 2 + 4 = 8$.
Sample 2
Input
3 3 1 2 1 4 2 3 1 5 1 3 1 6
Output
3
It is optimal to move through the vertices as $1$ → $2$ → $3$ → $1$, and the length of the shortest path is $1 + 1 + 1 = 3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。