백준 1956번) 최단경로 - 운동

 

 

 

최단경로 찾기 문제에서 간선에 음수가 있다면 벨만 포드, 

양수만 존재한다면 다익스트라, 양수중에서도 특정 구역을 거쳐서 지나간다면 플로이드 워셜 방법을 쓰도록 한다.

 

 

 

이 문제는 같은곳에서 출발하여 같은 곳으로 돌아온다는 것을 유의한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1e9


using namespace std;



int n, m;
int graph[401][401];



int main() {

	cin >> n >> m;
	for (int i = 0; i < 401; i++) {
		fill(graph[i], graph[i] + 401, INF);
	}

	//간선값 채워주기
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;
	}

	//플로이드 워셜
	for (int k = 1; k < n + 1; k++) {
		for (int a = 1; a < n + 1; a++) {
			for (int b = 1; b < n + 1; b++) {
				graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
			}
		}
	}

	int distance = INF;
	//같은자리에서 같은자리로 돌아오는 값중 최솟값찾아내기
	for (int i = 1; i < n + 1; i++) {

		distance = min(distance, graph[i][i]);

	}

	if (distance != INF) cout << distance << endl;
	else cout << "-1" << endl;

	return 0;


}