[BOJ]백준 1719번: 택배(C++)/FloydWarshall

https://www.acmicpc.net/problem/1719

1719번: 택배

이모티콘이 생겼다

 

택배 문제는 모든 정점에서 모든 정점으로의 최단 거리 및 최초 경유지를 구하는 문제이다

다익스트라와 플로이드와샬 두가지 방법 아무거나 사용해서 해결할 수 있다

map[i][j] = k

-> i번 집하장에서 j번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 k번 집하장으로 이동해야 한다

라고 할 때, distance가 갱신되는 시점에 해당 값을 update해주면 된다

#include <cstdio>
#include <vector>
#define INF 987654321
using namespace std;

int n, m;

int main() {
	scanf("%d%d", &n, &m);
	vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));
	vector<vector<int>> map(n + 1, vector<int>(n + 1, 0));

	for (int i = 0, u, v, w; i < m; i++) {
		scanf("%d%d%d", &u, &v, &w);
		dist[u][v] = w;
		dist[v][u] = w;
		map[u][v] = v;
		map[v][u] = u;
	}

	for (int i = 1; i <= n; i++) {
		dist[i][i] = 0;
		map[i][i] = i;
	}

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (dist[i][j] > dist[i][k] + dist[k][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
					map[i][j] = map[i][k];
				}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)printf("- ");
			else printf("%d ", map[i][j]);
		}			
		printf("\n");
	}
	return 0;
}