지하철 > 문제은행 : 정보올림피아드&알고리즘



2097 : 지하철

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
1919 회   
시도횟수
4778 회   

문제

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

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

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

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


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

입력형식

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

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

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

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

1번 역이 숙소가 있는 역이고, Sij에서 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

Hint!

최단거리알고리즘 정리 파일입니다.^^ 최단거리알고리즘.pdf


최단거리

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP