백준 11780 : 플로이드2

이번 문제는 정말 오랜만에 1트 AC받은 문제이다

이 문제를 풀 때의 주의점은, 1=>2 , 2=>1로 가는 가중치 경로가 있다 해도,

갱신하면 안 된다는 것 정도이려나

아래는 코드이다. 벡터 container를 이용한 merge연산을 통해 두 벡터를

합치는 방식을 썼다. 이는 집합을 합칠 때에서 착안했다.

#include<iostream>
#include<vector>
#define INF 1e9
using namespace std;
long long int n, m, map[101][101];
vector<int> path[101][101];
vector<int> merge(vector<int> v1, vector<int> v2){
	vector<int> v3;
	for(int i=0;i<v1.size();i++){
		v3.push_back(v1[i]);
	}
	for(int i=1;i<v2.size();i++){
		v3.push_back(v2[i]);
	}
	return v3;
}
//
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			map[i][j]=INF;
		}
	}
	for(int i=1;i<=m;i++){
		int b, c, d;
		cin >> b >> c >> d;
		if(map[b][c]<d) continue;
		map[b][c]=d;
		if(path[b][c].size()==0){
			path[b][c].push_back(b);
			path[b][c].push_back(c);
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j or i==k or j==k) continue;
				if(map[i][j]>map[i][k]+map[k][j]){
					map[i][j]=map[i][k]+map[k][j];
					path[i][j]=merge(path[i][k], path[k][j]);
				}
			}
		}
	}//floyd
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(map[i][j]==INF) cout << "0" << ' ';
			else cout << map[i][j] << ' ';
		}
		cout << '\n';
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(path[i][j].size()==0){
				cout << "0" << '\n';
				continue;
			}
			cout << path[i][j].size() << ' ';
			for(int k=0;k<path[i][j].size();k++){
				cout << path[i][j][k] << ' ';
			}
			cout << '\n';
		}
	}
}
//

오랜만에 쉬운 문제다! 플로이드 워셜 알고리즘은 O(N^3)이며, 여기에서 merge연산이 O(N)이라서

무난하게 통과된 것 같다. 2차원 배열 벡터를 써 본 것은 처음인데, 무난하게 통과되어 다행이라 생각한다.