플로이드 2

문제 링크

발상 & 풀이

Floyd - Warshall 알고리즘에 경로 역추적을 추가하는 문제다. 알고리즘 자체가 경로마다 모든 중간 정점을 끼워넣고 그 합계 비용을 검사하는 알고리즘이므로 경로 역추적도 저 중간 정점을 끼워넣은 새로운 경로가 최적일 때마다 그 경로로 갱신만 해주면 된다. 이전 문제들과 경로를 기록하는 구조가 달라서 조금 헷갈릴 수도 있지만 구조가 오히려 단순해서 직관적으로 생각하기는 더 쉽다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct eg {
	int v = 1e5+1;
	vector<int> p;
};
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m; vector<vector<eg>> dp(n + 1, vector<eg>(n + 1)); 
	for (int i = 1; i <= m; i++) {
		int s, e, c; cin >> s >> e >> c;
		if (dp[s][e].v < c) continue;
		dp[s][e].v = c;
		dp[s][e].p = { s, e };
	}	 
 
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j || j == k || k == i) continue;
				if (dp[i][j].v > dp[i][k].v + dp[k][j].v) {
					dp[i][j].v = dp[i][k].v + dp[k][j].v;
					dp[i][j].p = dp[i][k].p;
					dp[i][j].p.insert(dp[i][j].p.end(), dp[k][j].p.begin() + 1, dp[k][j].p.end());
				}
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << (dp[i][j].v == 1e5 + 1 ? 0 : dp[i][j].v) << " ";
		}
		cout << "\n";
	}
 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j || dp[i][j].p.size() == 0) {
				cout << "0\n";
			}
			else {
				cout << dp[i][j].p.size() << " ";
				for (auto p : dp[i][j].p) {
					cout << p << " ";
				}
				cout << "\n";
			}
		}
	}
	
	return 0;
}