[백준 11780] 플로이드 2 (C++)

문제 링크: https://www.acmicpc.net/problem/11780

11780번: 플로이드 2

1. 주의할 점

- 플로이드 와샬 알고리즘을 진행하면서 경로를 저장해야 빠르게 문제를 풀 수 있다

- 플로이드 와샬 알고리즘을 진행하면서 새로운 최단 경로가 생성되는 경우, I~K까지의 경로 + K~J까지의 경로를 I~J까지의 경로에 갱신해서 저장한다. 단, K가 2번 입력되지 않도록 설정한다

- 간선의 정보를 입력받을 때, I~J까지의 경로가 1가지가 아닐 수 있다

 

2. 구현

- Arr[][] 배열을 전부 MAX로 초기화한다. 단, I==J인 경우 0으로 초기화한다

- Arr[][] 배열을 통해 각 노드까지의 거리를 입력 받으며, 기존의 값보다 작은 경우에만 수정한다

- 플로이드 와샬을 수행하며 최단경로가 갱신될때 최단경로의 값, 최단경로에 이르기까지의 경로를 갱신한다

- Arr[][] 배열을 먼저 출력한 후, V[][] 벡터를 통해 경로를 출력한다

 

 

#define MAX 9876543210
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long arr[101][101];
vector<int> v[101][101];
int node, edge, s, e, val;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge;
	for(int i=1;i<=node;i++)
		for (int j = 1; j <= node; j++) {
			if (i == j) arr[i][j] = 0;
			else arr[i][j] = MAX;
			v[i][j].push_back(i);
			v[i][j].push_back(j);
		}
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		if(arr[s][e]>val)
			arr[s][e] = val;
	}

	for (int k = 1; k <= node; k++) {
		for (int i = 1; i <= node; i++) {
			for (int j = 1; j <= node; j++) {
				if (arr[i][j] > arr[i][k] + arr[k][j]) {
					arr[i][j] = arr[i][k] + arr[k][j];
					vector<int> t = v[k][j];
					v[i][j].clear();
					v[i][j] = v[i][k];
					for (int m = 1; m < t.size(); m++)
						v[i][j].push_back(t[m]);
				}
			}
		}
	}

	for (int i = 1; i <= node; i++) {
		for (int j = 1; j <= node; j++) {
			if (arr[i][j] == MAX) arr[i][j]=0;
			cout << arr[i][j] << " ";
		}
		cout << '\n';
	}

	for (int i = 1; i <= node; i++) {
		for (int j = 1; j <= node; j++) {
			if (arr[i][j] == 0)	cout << 0 << " ";
			else {
				cout << v[i][j].size() << " ";
				for (int k = 0; k < v[i][j].size(); k++)
					cout << v[i][j][k] << " ";
			}
			cout << '\n';
		}
	}
	return 0;
}