5 Problem A : 지하철

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

- 플로이드 와샬 N^3

- 다익스트라 대개 N^2

 

다익스트라 풀이

- D[] : 시작 점으로 인덱스까지의 최단 거리 저장 배열

- P[] : 값에서 인덱스까지 가는데 최단 거리를 가진 노드

- chk[] : 확정적으로 가장 짧은 거리 1로 변경

 

#include <stdio.h>
#define LN 11000

#define MAX 10

int N, M, S[MAX][MAX], D[MAX], P[MAX], chk[MAX];
// S는 입력 받는 행렬, D는 최단 거리 저장, P는 
void path(int pos)
{
	if (pos == 0) return;
	path(P[pos]);
	printf("%d ", pos);
}

int main(){
	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; // 도착지점에 오면 brek;
		for (i = 1; i <= N; i++) {
			if (D[i] > min + S[num][i]) {
				D[i] = min + S[num][i];
				P[i] = num; // num에서 i로 갈 때 가장 짧은 노드 저장
			}
		}
	}
	printf("%d\n", D[M]);
	path(M);
	return 0;
}

 

#include <stdio.h>

//#define MAX 110
#define MAX 6
int N, M, S[MAX][MAX], P[MAX][MAX];

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\n", S[1][M]); //최단 경로를 출력하고
	path(1, M);
	printf("%d\n", M);
	return 0;
}

 

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