Boj 11404) 플로이드

문제

백준 11404

설명

전형적인 플로이드 와샬문제.

시간복잡도

O(\(n^3\))

코드

int n;
int dp[101][101];

int main()
{
	fastio;

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


	for(int d = 1; d <= n; d++)
		for(int s = 1; s <= n; s++)
			for (int e = 1; e <= n; e++)
				if (dp[s][e] > dp[s][d] + dp[d][e])
					dp[s][e] = dp[s][d] + dp[d][e];
	
	for (int s = 1; s <= n; s++)
	{
		for (int e = 1; e <= n; e++)
			cout << (dp[s][e] == 100000000 || s == e ? 0 : dp[s][e]) << ' ';
		cout << endl;
	}
}