BOJ 1956: 운동

#BOJ 1956: 운동

1956번: 운동

#풀이

플로이드알고리즘을 통해서 해결할 수 있다.

 

플로이드를 계속 풀어서 그런가 그냥 모든게 다 플로이드로 보인다 ㅋㅋㅋ

 

 

그냥 d[i][j] + d[j][i] 의 최솟값을 출력해주면 된다.

 

i ==j, d[i][j] == INF, d[j][i] == INF 일 때 생각해서 처리를 해야한다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
int v, e;
int d[401][401];
const int INF = 0x3f3f3f3f;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> v >> e;
	for(int i = 1; i <=v; i++){
		fill(d[i] +1, d[i]+1+v,INF);
		d[i][i] = 0;
	}
	for(int i = 0; i < e; i++){
		int a, b, c;
		cin >> a>> b>> c;
		d[a][b] = c;
	}
	
	for(int k = 1; k <=v; k++){
		for(int i = 1; i <=v; i++){
			for(int j = 1; j <=v; j++){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	int ans = 0x3f3f3f3f;
	for(int i = 1; i <=v; i++){
		for(int j = 1; j <=v; j++){
			if(i == j)
				continue;
			if(d[i][j] == INF)
				continue;
			if(d[j][i] == INF)
				continue;
			ans = min(ans, d[i][j] + d[j][i]);
		}
	}
	if(ans == INF)
		ans = -1;
	cout << ans << '\n';
	return 0;
}