문제 출처

1. 문제설명

  • N개의 정점과 M개의 간선으로 이뤄진 그래프가 있다.

  • 모든 정점의 쌍(A, B)에 대해 A에서 B로 가는 비용의 최소값을 구하라.

  • 문제 분류
    • Graph, Floyd


2. 알고리즘 설계

  • 플로이드-워셜 알고리즘 기본 문제이다.
  • 해당 알고리즘은 $O(N^3)$이므로, 비교적 N이 작은 문제에서 동작한다.
    • 참고로, for문 1억번을 돌게되면 1초로 계산하면 된다.
  • 어떤 정점 간에는 간선이 없을 수도 있다.
    • 전부 엄청 큰 값 INF로 채우고, i==j의 경우 0이 된다.
  • 문제에서 같은 간선이 여러개 있을 수 있다고 했으니, 값을 저장할 때 비용의 최소값을 저장하면 된다.
    • arr[a][b] = min(arr[a][b], c)
  • 플로이드 알고리즘은 전부 계산해보면서, 값을 갱신해 나가는 알고리즘이다.
    • 구현 팁은 중간에 거치는 K를 for문의 가장 바깥쪽에 위치시켜야 한다는 것
  • 경로가 없다면 0을 출력한다. == INF인 경우 0


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int a, b, c, n, m, arr[102][102];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			arr[i][j] = (i==j ? 0 : INF);

	while(m--) {
		cin >> a >> b >> c;
		arr[a][b] = min(arr[a][b], c);
	}

	for(int k=1; k<=n; k++) 
		for(int i=1; i<=n; i++) 
			for(int j=1; j<=n; j++) 
				arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
	
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++)
			cout << (arr[i][j] == INF ? 0 : arr[i][j]) << ' ';
		cout << '\n';
	}

	return 0;
}