백준 11404 플로이드

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

 

 

이 문제는 최단경로 알고리즘중 하나인 플로이드 와샬 알고리즘을 통해서 해결하는 문제입니다.

 

모든정점과 다른정점들간의 최단경로를 구할때는 O(V^3)이 걸리는 플로이드 와샬 알고리즘이 가장 빠르기 때문에 이를

 

이용하면 되고 방법은 DP를 이용하여 dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]) 라는 점화식을 통하여

 

k정점을 경유하여 갈때와 기존의 저장된 값과 비교하여 더작은 값을 넣어주면 마지막에는 최단경로가 모두 저장되게 됩니다. 

 

#include <iostream>
#include <vector>

using namespace std;

#define INF 987654321
int V,m;
int adj[101][101];

void floyd() {
	for(int i = 1; i <= V; i++) adj[i][i] = 0;
	
	for(int k = 1; k <= V; k++)
		for(int i = 1; i <= V; i++)
			for(int j = 1; j <= V; j++) 
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
	return; 
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> V >> m;
	
	fill(&adj[1][1], &adj[V][V+1], INF);
	
	for(int i = 0; i < m; i++) {
		int a,b,c; cin >> a >> b >> c;
		if(adj[a][b] < c)
			continue;
		adj[a][b] = c;
	}
	floyd();
	
	for(int i = 1; i <= V; i++) {
		for(int j = 1; j <= V; j++) {
			if(adj[i][j] == INF)
				cout<<0<<' ';
			else
				cout<<adj[i][j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}