백준 11780 플로이드2

문제링크

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

문제

풀이

플로이드 와샬 + 경로추적 문제이다.

1. 먼저 경로를 저장할 2차원 벡터 배열을 선언한다.

2. 그리고 플로이드 와샬 알고리즘 수행 중 maps[i][k]+maps[k][j]<maps[i][j] 인 상황에서 값이 갱신 될 때, 경로도 함깨 갱신 되도록 했다.

3. 경로는 route[i][j] : route[i][k] 경로 + route[k][j] 경로
   이 과정에서 vector의 insert 함수를 이용해 두 벡터를 합쳐주었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long ll;
#define INF 1000000
int n, m;
int maps[101][101];
vector<int> route[101][101];
void init() {
	fill(&maps[0][0], &maps[100][101], INF);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	init();


	cin >> n >> m;
	
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (maps[a][b] > c) {
			maps[a][b] = c;
			route[a][b] = { a,b };
		}
		
	}


	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) continue;
				if (maps[i][k] + maps[k][j] < maps[i][j]) {
					maps[i][j] = maps[i][k] + maps[k][j];
					route[i][j] = route[i][k];
					route[i][j].insert(route[i][j].end(), route[k][j].begin()+1, route[k][j].end());
				}
			}
		}
	}
	

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

	for(int i=1;i<=n;i++){
		for (int j = 1; j <= n; j++) {
			cout << route[i][j].size()<<' ';
			for (int k = 0; k < route[i][j].size(); k++) {
				cout << route[i][j][k] << ' ';
			}
		cout << '\n';
		}
	}

}

후기

vector의 insert 함수를 이용한 두 벡터를 합치는 방법에 대해 처음 알았다.
플로이드 와샬 알고리즘 복습 기회