백준 11780 c++ "플로이드 2" -[PlusUltraCode]

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

11780번: 플로이드 2

[필자 사고]

이 문제는 다익스트라, 플로이드 둘다 사용해서 풀 수 있는 문제이다.

 

필자는 플로이드 와샬을 이용해서 풀었다.

 

주의할 점은 초기 배열에 값을 저장할때 Arr[i][k]= min(Arr[i][k],w); 이 작업을 반드시 해야 된다.

 

입력값이 기존보다 더 작은값이 들어올수도 있기 때문이다.

 

또한 parent배열의 경로를 찾을때는 아래코드가 핵심이니 기억해두자.

 

while(st!=j){

  path.push(st);
  st=pareht[st][j];
}

 

쉽게 말하면 1->3->5 와 같은 경로를 순서대로 밟아가는 과정이라 생각하면 된다.

parent[start][nextIdx] = parent[start][nowIdx];

 

특정 조건이 성립했을 때는 위와 같은 코드로 부모노드를 갱신해줘야 된다. 반드시.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include<climits>
using namespace std;

int N, M;
vector<vector<long>> Arr;
const long INF = 987654321;
vector<vector<int>> parent;


void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	parent.resize(N + 1);

	for (int i = 0; i <= N; i++) {
		Arr[i].resize(N + 1, INF);
		parent[i].resize(N + 1);
	}
	for (int i = 0; i <= N; i++) {
		for (int k = 0; k <= N; k++) {
			parent[i][k] = k;
		}
	}
	for (int i = 0; i < M; i++) {
		int s, e;
		long w;
		cin >> s >> e >> w;
		if (Arr[s][e] > w) {
			Arr[s][e] = w;
			
		}
		;
		
	}

	

	for (int i = 0; i <= N; i++) {
		Arr[i][i] = 0;
	}
}

void Floyd_Warshall() {
	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				if (s == e)continue;
				if (Arr[s][e] > Arr[s][k] + Arr[k][e]) {
					Arr[s][e] = Arr[s][k] + Arr[k][e];
					parent[s][e] = parent[s][k];
				}

			}
		}
	}
	
}
void Print() {
	for (int s = 1; s <= N; s++) {
		for (int e = 1; e <= N; e++) {
			if (s == e||Arr[s][e]==INF) {
				cout << 0 << " ";
				continue;
			}
			cout << Arr[s][e] << " ";

		}
		cout << '\n';
	}
}

void FindParent(int i,int j) {
	if (Arr[i][j] == 0 || Arr[i][j] == INF) {
		cout << "0\n";
		return;
	}
	vector<int> path;
	int st = i;
	while (st != j) {
		path.push_back(st);
		st = parent[st][j];
	}
	path.push_back(j);
	cout << path.size() << ' ';
	for (auto x : path) cout << x << ' ';
	cout << '\n';
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Floyd_Warshall();
	Print();

	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			FindParent(i, k);
		}
	}
}