Problem C
Cross Country
Charles Johnson is on his way to meet his very good friend Bernard Terrell. They are going on their bi-weekly skiing trip. Today Charles had forgot all about the Kvikk Lunsj and had to go back home to get it. This has left him very late, and to make things worse all the parking spots close to the meeting spot has been taken. Given the workout diary of Charles, could you help find the fastest path to the meeting spot?
Input
The first line of the input consists of three
space-separated integers $N$, $S$, $T$, representing the number of
intersections in the ski tracks networks, the index of the
intersection where Charles parked his car and the index of the
intersection where Charles agreed to meet Bernard.
Then follows $N$ lines.
Each of the lines consists of $N$ space-separated integers
$D_{ij}$. The integer on
line $i$ and column
$j$ describes the time in
minutes it takes for Charles to get from intersection
$i$ to intersection
$j$.
Output
The output should be a single line consisting of the minimum number of minutes Charles will have to use to get to the meeting point to share some Kvikk Lunsj with Bernard.
Limits
-
$1 \leq N \leq 1\, 000$
-
$0 \leq S, T < N$
-
$1 \leq D_{ij} < 10\, 000$ for $i \ne j$
-
$D_{ii} = 0$
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 3 0 1 3 14 2 0 4 22 3 10 0 7 13 8 2 0 |
11 |
