백준 11780 플로이드 2 C++

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

11780번: 플로이드 2

예전에 푼 문제인데 재채점하니 틀렸다 그래서 다시 풀었습니다. (아마 문제 조건이 조금 추가된 듯하다.)

 

다익스트라 알고리즘은 한 정점에서 모든 정점으로의 최단 거리 (가중치 양수),

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로 가는 최단 거리를 찾는 문제입니다.

 

초기 입력값이 주어질 때, 연결되지 않은 지점은 inf 로 처리 후, 모든 정점을 중간 노드로 설정하여 모든 출발 정점과 도착 정점에 대해 탐색을 합니다. 이 때 기존 경로보다 새 경로가 작은 경우 업데이트해주면 됩니다.

 

간단한 수도 코드는 다음과 같습니다.

 

dist[n][n] : n 개 노드 간의 가중치, 입력 없을 시 무한대

i : 중간 노드 역할, j : 출발 노드, k : 도착 노드

 

for i 1 to n : 

     for j 1 to n :

          for k 1 to n :

               if dist[ j ][ k ] > dist[ j ][ i ] + dist[ i ][ k ] :

                      dist[ j ][ k ] =  dist[ j ][ i ] + dist[ i ][ k ]               

 

문제에서는 최단 거리일 때 경로도 출력하라고 하였으므로, 위에서 경로가 업데이트 될 때마다 j to i 인 경로에 i to k 인 경로를 추가해주면 됩니다. (중간 노드는 겹치므로 i 는 하나만)

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, m;
int dist[101][101]; // [i][j] : i to j 최소 비용
vector<int> station[101][101]; // [i][j] : i to j 거쳐가는 곳
int inf = 987654321;

void init()
{
	cin >> n;
	cin >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist[i][j] = inf;
		}
	}

	for (int i = 1; i <= m; i++) {
		int a, b, c; // a to b , cost
		cin >> a >> b >> c;
		if (dist[a][b] != inf) {
			if (dist[a][b] > c) {
				dist[a][b] = c;
			}
		}
		else {
			dist[a][b] = c;
			station[a][b].push_back(a);
			station[a][b].push_back(b);
		}
	}
}

void Floyd_Warshall()
{
	// i : 중간 노드, j :  출발 노드, k : 도착 노드
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {

				// 시작, 끝 같은 경우 없음.
				if (j == k) {
					continue;
				}

				if ((dist[j][i] + dist[i][k]) < dist[j][k]) {
					dist[j][k] = dist[j][i] + dist[i][k];
					vector<int> v;
					v = station[j][i];
					for (int s = 1; s < station[i][k].size(); s++) {
						v.push_back(station[i][k][s]);
					}
					station[j][k] = v;
				}
			}
		}
	}
}

void print_dist()
{
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == inf) {
				cout << 0 << ' ';
			}
			else {
				cout << dist[i][j] << ' ';
			}
		}
		cout << '\n';
	}
}

void print_station()
{
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == inf) {
				cout << 0 << '\n';
			}
			else {
				cout << station[i][j].size() << ' ';
				for (int k = 0; k < station[i][j].size(); k++) {
					cout << station[i][j][k] << ' ';
				}
				cout << '\n';
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	init();
	Floyd_Warshall();

	print_dist();
	print_station();
}