페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2097
스페셜 저지

지하철 1s 64MB

문제

지방에서 서울에 관광온 도훈이는 지하철 노선을 보고 깜짝 놀랐다. 

노선이 엄청나게 복잡하기 때문이었다. 

각 노선들이 서로 얽혀있어서 잘못하면 10분도 안걸리는 거리를 1시간 동안 갈 수도 있는 상황이었다.  

어쩔 수 없이 도훈이​는 현재 숙소에서 관광할 목적지까지 가장 짧은 시간에 도착할 수 있는 경로와 시간을 표로 만들려고 한다.

 

단, 각 지하철역에 관광지가 있고, 지하철을 갈아타는데 소요되는 시간은 없다고 가정한다.


입력

첫줄에 N(3≤N≤100), M(1≤M≤N)을 입력 받는다. 

N은 지하철역의 수, M은 원하는 목적역의 번호를 입력받는다. 

둘째 줄부터 N개의 줄이 나오고, 각 줄에는 N개의 수 S가 입력된다. 

i번째 줄에서 j번째 수 S_{ij}는 i번역에서 j번 역까지 가는데 걸리는 시간이다. 

1번 역이 숙소가 있는 역이고, S_{ij}에서 i = j 일 때는 항상 0 이다. (0≤S≤100)


출력

목적 역까지 가는데 걸리는 최소 시간과 최소시간으로 가는 최단경로를 출력한다.


예제 

5 5

0 2 2 5 9

2 0 3 4 8

2 3 0 7 6

5 4 7 0 5

9 5 6 5 0
8

1 3 5



로그인해야 코드를 작성할 수 있어요.