지하철 > 문제은행

본문 바로가기


알고리즘 최단거리

2097 : 지하철

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 1312 회    시도횟수: 3715 회    Special Judge



지방에서 서울에 관광온 성수는 지하철 노선을 보고 깜짝 놀랐다. 노선이 엄청나게 복잡하기 때문이었다. 각 노선들이 서로 얽혀있어서 잘못하면 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)


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

[Copy]
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
[Copy]
8
1 3 5



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



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.