[백준 11404번 C/C++] 플로이드

 

[백준 11404번 C/C++] 플로이드

 

 

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

 

11404번: 플로이드

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가

www.acmicpc.net

---

 

 

해결전략

 

플로이드 워셜 Floyd-Warshall Algorithm

 

---

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m;
vector<vector<int>>dist;
 
const int INF = 2147000000 / 2;//최댓값 설정
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n >> m;
	dist.resize(n+1, vector<int>(n+1, INF));//기본값을 최댓값
	int a, b, c;
 
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
 
		if(dist[a][b] > c) 
			dist[a][b] = c;
	}
 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dist[i][j] = 0;
		}
	}
 
	for (int k = 1; k <= n; k++) 
	{
		for (int i = 1; i <= n; i++) 
		{
			for (int j = 1; j <= n; j++) 
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
	
	for (int start = 1; start <= n; start++) 
	{
		for (int end = 1; end <= n; end++) 
		{
			//값이 최댓값이라는건 바뀐적이 없다는 의미(=길이 없다는 의미)
			if (dist[start][end] == INF)
				cout << "0" << " ";
			else
				cout << dist[start][end] << " ";
		}
		cout << "\n";
	}
 
	return 0;
}

 

---