Graph II - Single Source Shortest Path II

Time Limit : 1 sec, Memory Limit : 131072 KB

Pn_ŒZoH II

^ꂽdݕtLOt $G = (V, E)$ ɂāAPn_ŒZoH̃RXg߂vO쐬ĂB$G$ ̒_ $0$ n_ƂA$0$ e_ $v$ ɂāAŒZoH̕ӂ̏d݂̑a $d[v]$ o͂ĂB

ŏ̍s $G$ ̒_ $n$ ^܂B $n$ sŊe_ $u$ ̗אڃXgȉ̌ŗ^܂F

$u$ $k$ $v_1$ $c_1$ $v_2$ $c_2$ ... $v_k$ $c_k$

$G$ ̊e_ɂ $0$ $n-1$ ̔ԍӂĂ܂B$u$ ͒_̔ԍłA$k$ $u$ ̏o܂B$v_i (i = 1, 2, ... k)$ $u$ ɗאڂ钸_̔ԍłA$c_i$ $u$ $v_i$ ȂLӂ̏d݂܂B

o

e_̔ԍ $v$ Ƌ $d[v]$ P̋󔒋؂ŏԂɏo͂ĂB

• $1 \leq n \leq 10,000$
• $0 \leq c_i \leq 100,000$
• $|E| < 500,000$
• 0 em[hւ͕KoH݂

͗ 1

5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3


o͗ 1

0 0
1 2
2 2
3 1
4 3
`

Ql

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.