BOJ 11404: 플로이드

#BOJ 11404: 플로이드

11404번: 플로이드

#풀이

문제 제목을 보고 알 수 있듯이 플로이드 알고리즘을 통해서 쉽게 해결할 수 있는 문제이다.

 

 

플로이드 알고리즘은 그래프에서 최단거리의 비용을 찾는 알고리즘 중 하나이다.

 

추후에 블로그에 플로이드 알고리즘을 올릴 예정이다.

 

인접행렬을 통해서 i->j 까지의 거리의 최단 거리를 찾아야 한다.

 

하지만 i->j까지 가는 거리가 중간에 아무 정점을 거치지 않고 갈 수 도 있지만 중간 s라는 정점을 거쳐서 가는 방법이 있을 수도 있다.

 

i->s + s->j , i->j 이 둘 중에 더 적은 비용을 인접행렬에 저장하면 된다.

 

#코드

 

#include<bits/stdc++.h>

using namespace std;
int n, m;
int adj[101][101];
int INF = 0x3f3f3f3f;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	cin >> m;
	for(int i= 0; i <m; i++){
		int a, b, c;
		cin >> a>>b>>c;
		if( adj[a][b] == 0 || adj[a][b] > c) 
			adj[a][b] = c;	
	}
	
	for(int i = 1; i<=n; i++){
		for(int j = 1; j <=n; j++){
			if(i!=j && adj[i][j] == 0) 
				adj[i][j] = INF;
		}
	}
	
	for(int k = 1; k<=n; k++){
		for(int i = 1; i<=n; i++){
			for(int j = 1; j<=n; j++){
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
			}
		}
	}
	
	for(int i = 1; i<=n; i++){
		for(int j = 1; j <=n; j++){
			if(adj[i][j] == INF)
				cout << 0 << ' ' ;
			else
				cout << adj[i][j] << ' ';
		}
		cout << '\n';
	}
		
	return 0;
}