알고리즘 문제

[백준] 11404번 플로이드

feelcoding 2020. 2. 7. 13:58
728x90

그 유명한 플로이드(Floyd) 알고리즘이다.

 

11404번: 플로이드

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작

www.acmicpc.net

주의할 점은 n에서 m으로 가는 이음선이 여러 개가 있을 수 있다는 것이다. 따라서 가중치를 입력받을 때 작은 값만 배열에 저장하도록 해야 한다.

플로이드 알고리즘은 아래 글에서 자세히 설명해놓았다.

https://breakcoding.tistory.com/148

 

[알고리즘] 플로이드 (Floyd) 알고리즘

최단경로 알고리즘은 플로이드 알고리즘과 다익스트라 알고리즘이 가장 대표적인 두 알고리즘이다. 다익스트라 알고리즘은 출발지가 주어졌을 때 그 출발지(one)로부터 모든 지점(all)으로 가는

breakcoding.tistory.com

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, e;
	cin >> n >> e;
	const int INF = 100001;
	vector<vector<int>> d(n + 1, vector<int>(n + 1, INF));
	for (int i = 1; i <= n; i++) {
		d[i][i] = 0;
	}
	for (int i = 0; i < e; i++) {
		int from, to, weight;
		cin >> from >> to >> weight;
		if(d[from][to] == 0 || d[from][to] == INF)
			d[from][to] = weight;
		else d[from][to] = min(weight, d[from][to]);
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (d[i][j] == INF) cout << 0 << " ";
			else cout << d[i][j] << " ";
		}
		cout << '\n';
	}
	return 0;
}
728x90