백준 11404번 플로이드

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

11404번: 플로이드

dire[a][b]는 a번 노드에서 b번 노드로 가는 비용을 담아둔다.

i, j, N을 차례로 반복문에 돌려서 j에서 i를 거쳐 N으로 가는 최단경로를 갱신해준다.

 

#include<iostream>
#include<algorithm>
using namespace std;

int dire[100][100];
//초기에 정점간의 거리들을 초기화 해줄 수
const int INF = 987654321;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, a, b, c;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dire[i][j] = INF;
		}
	}
	for (int i = 0; i < n; i++) {
		dire[i][i] = 0;
	}

	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		a -= 1;
		b -= 1;
		dire[a][b] = min(dire[a][b], c);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int N = 0; N < n; N++) {
				if (j == N) continue;
                //j에서 i 혹은 i에서 N으로 가는 경로가 없을 때
				if (dire[j][i] == INF || dire[i][N] == INF) continue;
                //최단경로 갱신
				dire[j][N] = min(dire[j][N], dire[j][i] + dire[i][N]);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
        	//갈 수 없을 때
			if (dire[i][j] == INF) cout << 0 << ' ';
			else cout << dire[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}