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

 

 

<코드>

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

#define INF 10000001

int dp[101][101];
int n, m, a, b, c;

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


	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i != j) dp[i][j] = INF;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		dp[a][b] = min(dp[a][b], c);
	}

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			

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

 

풀이 방법

 

비용의 최대값은 9,900,000이며, 노선이 하나가 아닐 수 있다는 사실에 주의합시다.

 

www.acmicpc.net/problem/11404

11404번: 플로이드