[백준 11657] 타임 머신

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

11657번: 타임머신

요구사항

음의 경로가 있는지 확인(벨만 포드)

 

풀이

모든 노드에 대해서 간선만큼 반복하여 최저 경로를 갱신한다

모든 노드에 대해서 탐색하고 한번 더 탐색하였을 때, 감소되는 경로가 있으면 음의 경로가 존재하는 것이다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
struct go {
	int x;
	int y;
};
int n, m;
int dist[501];
vector<go> v[501];
const int INF = 0x7fffffff;
int main() 
{
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		v[x].push_back({ y,z });
	}
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	dist[1] = 0;
	int flag = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (auto p : v[j]) {
				int next = p.x;
				int D = p.y;
			//	cout << next << " " << D << endl;
				if (dist[j] != INF && dist[next] > dist[j] + D)
				{
					dist[next] = dist[j] + D;
					if (i == n) flag = 1;
				}
				
			}
		}
	}
	if (flag == 1)
		cout << "-1" << endl;
	else {
		for (int i = 2; i <= n; i++) {
			printf("%d\n", dist[i] != INF ? dist[i] : -1);
		}
	}
	
}