[백준] 11404번 플로이드

링크

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

11404번: 플로이드

풀이

 

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 문제이다.

 

일단 제목에서 플로이드 워셜 알고리즘으로 풀어야 되겠구나 라는 것을 알 수 있지만.

경로 찾는 알고리즘인 다익스트라, 벨만 포드를 써도 문제는 풀 수 있다.

 

일단 플로이드워셜의 시간 복잡도는 o(n^3) 이기 때문에 도시의 개수가 중요하다.

 

도시의 갯수가 100개 이므로 플로이드 워셜로 충분히 풀리는 문제이다.

 

일단 모든 도시로 갈 수 있는 경로를 결과로 나올 수 없는 최대 값으로 초기화를 해주고

출발지와 도착지는 같은 점이 될 수 없기 때문에 모두 0으로 초기화를 해준다.

 

플로이드 워셜은 도시 a 에서 도시 b로 갈 때 

a에서 b로 가는 경로중 경유지 k를 방문했을 때 최소 값을 계속 갱신해 나가는 알고리즘이다.

 

그래서

도시[a][b] = min(도시[a][b] , 도시[a][k] + 도시[k][b]) 라는 식을 만들 수 있다.

 

#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstring>
#include<string>

#define SIZE 110
using namespace std;

int INF = 2e7;
int city[SIZE][SIZE];

void init() {
	for (int i = 0; i < SIZE; i++) {
		for (int j = 0; j < SIZE; j++) {
			if (i == j) {
				city[i][j] = 0;
				continue;
			}
			city[i][j] = INF;
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M; cin >> N >> M;

	init();

	for (int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c;
        //출발지와 도착지가 같을 경우 작은 경로로 갱신
		city[a][b] = min(city[a][b], c);
	}

	//경유지
	for (int k = 1; k <= N; k++) {
    	//출발지
		for (int i = 1; i <= N; i++) {
        	//도착지
			for (int j = 1; j <= N; j++) {
				if (i == j)continue;
				city[i][j] = min(city[i][j], city[i][k] + city[k][j]);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << (city[i][j] == INF ? 0 : city[i][j]) << " ";
		}
		cout << "\n";
	}

}