# Shortest Path - Single Source Shortest Path (Negative Edges)

Ԑ : 1 sec, : 131072 KB
pł͂

# Pn_ŒZoHȉd݂ӂ܂ށj

^ꂽOt $G = (V, E)$ Ǝn_ $r$ ɂāAPn_ŒZoH̏d݂߂vO쐬ĂB$G$ ̃m[h $r$ n_ƂA$r$ em[hɂāAŒZoH̕ӂ̏d݂̑ao͂ĂB

$|V| \; |E| \; r$
$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$r$ ͎n_̔ԍłB

$s_i$, $t_i$ ̓Ot $G$ $i$ Ԗڂ̕ӂԂQ̒_\iLjB$d_i$ $i$ Ԗڂ̕ӂ̏d݂łB

## o

$G$ ɂāA$r$ H镉̕HioH̕ӂ̏d݂̘aɂȂ悤ȕHj݂ꍇ NEGATIVE CYCLE ƂPsɏo͂B

̂悤ȕH݂ȂꍇAe_ $0, 1, ..., |V|-1$ ɂāAn_ $r$ ̍ŒZoH̏d݂̑aԂɏo͂BA$r$ ̌oH݂Ȃꍇ INF Əo͂B

• $1 \leq |V| \leq 1000$
• $0 \leq |E| \leq 2000$
• $-10000 \leq d_i \leq 10000$
• $G$ ɕsӂ͂Ȃ
• $G$ Ɏȃ[v͂Ȃ

## ͗ 1

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


## o͗ 1

0
2
-3
-1


## ͗ 2

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


## o͗ 2

NEGATIVE CYCLE


## ͗ 3

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


## o͗ 3

INF
0
-5
-3