[백준 1719번] 택배

문제 링크: https://www.acmicpc.net/problem/1719

1719번: 택배

<문제 풀이> 플로이드-워셜 알고리즘

 

 

nxt[i][j] : i에서 j로의 최단 경로를 따라 i에서 가장 먼저 방문해야 하는 정점

 

이와 같은 2차원 배열 nxt를 추가로 정의하여 플로이드 알고리즘을 수행합니다.

 

i에서 j로 이동하는 경로에서 새로운 최단 거리를 갱신하는 장점 k를 찾게 되면, nxt[i][j] = nxt[i][k]로 nxt 배열을 갱신합니다.

 

이는 i에서 k로의 최단 경로를 따라 이동한 후, k에서 j로의 최단 경로를 이동하기 때문입니다. 따라서 i에서 j로 이동할 때 가장 먼저 방문해야 하는 정점은 i에서 k로 이동할 때 가장 먼저 방문해야 하는 정점인 nxt[i][k]와 같습니다.

 

 

<C++소스코드>

 

#include<iostream>
#include<cstring>
using namespace std;

const int MAX_N = 200;
int n, m;
int graph[MAX_N + 1][MAX_N + 1];
int nxt[MAX_N + 1][MAX_N + 1];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;
	memset(graph, 0x3f, sizeof(graph));
	for (int i = 1; i <= n; i++) {
		graph[i][i] = 0;
	}
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		graph[u][v] = w;
		graph[v][u] = w;
		nxt[u][v] = v;
		nxt[v][u] = u;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][j] > graph[i][k] + graph[k][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
					nxt[i][j] = nxt[i][k];
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (nxt[i][j] == 0) cout << "- ";
			else cout << nxt[i][j] << " ";
		}
		cout << '\n';
	}

	return 0;
}