[G4] 백준 1956번 운동 C++ 최단 경로, 플로이드 와샬

리뷰

 

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

단방향 간선으로 이루어진 그래프에서의 싸이클을 이루는 최단 거리를 구하는 문제

 

 

전역 변수

• V : 배열의 최대 크기를 정의할 상수 변수
• dist : 노드간 최단 거리를 저장할 2차원 배열
• v : 정점의 개수를 저장할 변수
• e : 간선의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. v, e값을 입력 받고, dist배열을 매우 큰 값으로 초기화한다. 이 때 자기 자신으로의 거리는 0으로 한다.
2. e개의 간선 정보를 입력 받아 dist배열을 최신화한다.
3. 플로이드 와샬 알고리즘을 수행하여 노드간 최단 거리를 구해준다.
4. 변수 mn을 거리의 초기값으로 초기화하고, 노드간 경로 중 최소값을 mn에 갱신한다.
5. 이때 자기 자신으로의 경로나 간선이 존재하지 않은 경우 continue처리한다.
6. 최종적으로 mn의 값이 초기값이라면 -1을, 아니라면 mn을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 단방향 도로 환경에서 시작점으로 다시 돌아오는 경우를 찾아야 한다. 시작 노드와 도착 노드는 정해져 있지 않다.

 

정답 코드

#include<iostream>
using namespace std;

const int V = 401;
int dist[V][V];
int v, e;

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

	cin >> v >> e;
	for (int i = 1; i <= v; ++i)
		for (int j = 1; j <= v; ++j)
			dist[i][j] = i == j ? 0 : 1e9;

	while (e--) {
		int f, t, w; cin >> f >> t >> w;
		dist[f][t] = w;
	}
	for (int k = 1; k <= v; ++k) {
		for (int i = 1; i <= v; ++i) {
			for (int j = 1; j <= v; ++j) {
				if (dist[i][k] == 1e9 || dist[k][j] == 1e9) continue;
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	int mn = 1e9;
	for (int i = 1; i <= v; ++i) {
		for (int j = 1; j <= v; ++j) {
			if (i == j) continue;
			if (dist[i][j] == 2e9 || dist[j][i] == 2e9) continue;
			mn = min(mn, dist[i][j] + dist[j][i]);
		}
	}
	cout << (mn == 1e9 ? -1 : mn);
}