# Shortest Path - All Pairs Shortest Path

Ԑ : 1 sec, : 131072 KB
pł͂

# S_ΊԍŒZoH

dݕtLOt $G = (V, E)$ ̑S_ΊԍŒZoH̋񋓂ĂB

͈͂ȉ̌ŗ^܂B

$|V|\; |E|$
$s_0\; t_0\; d_0$
$s_1\; t_1\; d_1$
$:$
$s_{|E||1}\; t_{|E||1}\; d_{|E|-1}$

$|V|$, $|E|$ ͂ꂼOt $G$ ̒_̐ƕӂ̐܂BOt $G$ ̒_͂ꂼ $0, 1, ..., |V|-1$ ̔ԍtĂ̂Ƃ܂B

$s_i$, $t_i$, $d_i$ ̓Ot $G$ $i$ Ԗڂ̕ӂԁiLjQ̒_̔ԍƂ̏d݂\܂B

## o

Ot $G$ ̕Hiӂ̏d݂̘aɂȂ悤ȕHjꍇ NEGATIVE CYCLE ƂPsɏo͂ĂBȊȌꍇȉ̌ŋo͂ĂB

$D_{0,0}\; D_{0,1}\; ...\; D_{0,|V||1}$
$D_{1,0}\; D_{1,1}\; ...\; D_{1,|V||1}$
:
$D_{|V||1,0}\; D_{|V|-1,1}\; ...\; D_{|V||1,|V||1}$

o͂ $|V|$ sȂ܂B$i$ sڂɒ_ $i$ e_ $j\; (j = 0, 1, ...|V|-1)$ ւ̍ŒZoH̋o͂ĂB$i$ $j$ ւ̌oHȂꍇ INF Əo͂ĂB̊ԂɂP̋󔒂o͂ĂB

• $1 \leq |V| \leq 100$
• $0 \leq |E| \leq 9,900$
• $-2 \times 10^7 \leq d_i \leq 2 \times 10^7$
• $G$ ɑdӂ͂Ȃ
• $G$ Ɏȃ[v͂Ȃ

4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 7

0 1 3 4
INF 0 2 3
INF INF 0 1
INF INF 7 0

4 6
0 1 1
0 2 -5
1 2 2
1 3 4
2 3 1
3 2 7

0 1 -5 -4
INF 0 2 3
INF INF 0 1
INF INF 7 0

4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 -7

NEGATIVE CYCLE