백준 11404번 플로이드

< 백준 11404번 플로이드 - 마포 코딩박 >

사용한 알고리즘: 플로이드 와샬


 N개의 도시와 도시를 이동하는 버스들의 정보가 주어졌을 때, 임의의 도시 a 에서 도시 b 로 이동하는 비용을 구하는 문제였습니다.
 N이 최대 100으로 작게 주어지고, 각 도시간 이동을 구하는 문제로, 플로이드-와샬로 문제를 해결하였습니다.

풀이는 다음과 같습니다.

(1) (코드 8~9, 14~17)
 'cost[a][b] : a->b 이동하는 비용' 이라고 설정하고, 자기자신으로 이동하는 비용은 0, 나머지는 Infimum 으로 초기화했습니다.

(2) (코드 23~26)
 플로이드와샬은 사실 이 3중 for문으로 끝납니다.
 i->j 갈때, i->k->j 로 중간에 k 들렸다 가는게 작으면 값을 최신화해줍니다.

	#include <iostream>
	#include <algorithm>
	using namespace std;
	// 플로이드 와샬
	const int INF = 999999999;
	int TC, N, M;
	// cost[a][b] : a->b 이동하는 비용
	int cost[101][101];
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	// 초기화
	for (int i = 1; i <= N; ++i)
	for (int j = 1; j <= N; ++j)
	cost[i][j] = i==j? 0 : INF;
	for (int i = 0; i < M; ++i){
	int s,e,t;
	cin >> s >> e >> t;
	cost[s][e] = min(cost[s][e],t);
	}
	for (int k = 1; k <= N; ++k)
	for (int i = 1; i <= N; ++i)
	for (int j = 1; j <= N; ++j)
	cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
	for (int i = 1; i <= N; ++i){
	for (int j = 1; j <= N; ++j)
	cost[i][j]==INF? cout << 0 << ' ' : cout << cost[i][j] << ' ';
	cout << '\n';
	}
	return 0;
	}

view raw BOJ 11404.cpp hosted with ❤ by GitHub