5 Problem A : 지하철

Problem A : 지하철

 

제한시간: 1000 ms    메모리제한: 64 MB
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)

 

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

 

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

 

// dijkstra
#include <stdio.h>
#define LN 11000

int N, M, S[110][110], D[110], P[110], chk[110];

void path(int pos)
{
	if (pos == 0) return;
	path(P[pos]); // 지나간 경로 재귀로 풀어냄
	printf("%d ", pos);
}

int main()
{
	freopen("input.txt", "r", stdin);
	int i, j, k, min, num;
	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) scanf("%d", &S[i][j]);
		D[i] = LN;
	}
	D[1] = 0; 

	while (1) {
		min = LN; // 최대값으로 초기화해 둠
		for (i = 1; i <= N; i++) {
			if (chk[i] == 0 && D[i] < min) { // 확정 되지 않고, 가장 짧은 거리를 찾음
				min = D[i]; // 누적값이 들어감
				num = i;
			}
		}
		chk[num] = 1; // 여긴 확정
		if (num == M) break; // 여긴 목적지와 비교
		for (i = 1; i <= N; i++) {
			if (D[i] > min + S[num][i]) { // 가장 작은 경로를 찾음
				D[i] = min + S[num][i]; // 지금 선택된 num에서 연결된 곳 까지 거리를 저장함
				P[i] = num; // 어디서 온 것인지 확인하기 위한 용도
			}
		}
	}
	printf("%d\n", D[M]);
	path(M);
	return 0;
}

/* floyd
#include <stdio.h>

int N, M, S[110][110], P[110][110];

void path(int s, int e)
{
if (P[s][e] == 0) return;
path(s, P[s][e]);
printf("%d ", P[s][e]);
path(P[s][e], e);
}

int main()
{
int i, j, k;
scanf("%d %d", &N, &M);
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++) scanf("%d", &S[i][j]);

for (k = 1; k <= N; k++)
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++) {
if (S[i][j] > S[i][k] + S[k][j]) {
S[i][j] = S[i][k] + S[k][j];
P[i][j] = k;
}
}

printf("%d\n1 ", S[1][M]);
path(1, M);
printf("%d\n", M);
return 0;
}
*/