Hide

Problem N
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

Please log in to submit a solution to this problem

Log in