BOJ 11780 - 플로이드2

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned long long ll;
const int INF = 1e9;

int dist[101][101];
int via[101][101];
int ks[101][101];

void reconstruct(int i, int j, vector<int>& path) {
	//i->j 경유없이 가는 경우면
	if (via[i][j] == -1) {
		path.push_back(i+1);
		path.push_back(j+1);
		return;
	}

	//i->j 경유점이 있다면
	int w = via[i][j]; //w에 경유점 담아주고
	reconstruct(i, w, path);
	path.pop_back();
	reconstruct(w, j, path);

}

int main() {
	int n, m; scanf("%d %d", &n, &m);
	
	fill(&via[0][0], &via[100][101], -1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j] = i == j ? 0 : INF;
		}
	}
	for (int i = 0,u,v,w; i < m; i++) {
		scanf("%d %d %d", &u, &v, &w);
		dist[u-1][v-1] = min(dist[u - 1][v - 1], w);
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (dist[i][j] > dist[i][k] + dist[k][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
					via[i][j] = k;
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d ", dist[i][j]);
		}
		printf("\n");
	}
			
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dist[i][j] >= INF || dist[i][j]==0) {
				printf("0\n");
				continue;
			}
			vector<int> path;
			reconstruct(i, j, path);
			printf("%d ", path.size());
			for (int num : path) printf("%d ", num);
			printf("\n");
		}
	}
		

}

 

같은 경로지만 다른 가중치가 들어오는 경우가 있는 특이 케이스.

 

플로이드 3중for문 내부

dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]) 부분에 via[i][j]=k를 달아줘서 경유점 저장해 둠.

마지막에 저장되는 k값만이 유효함.

 

reconstruct 함수를 짜는 것 외워둘 필요가 있어 보인다.