[C++] 백준 11657번 타임머신

A라는 도시에서 나머지 도시들을 가장 빠르게 가는 길을 구하는 문제입니다.
거리에 대한 음수값이 존재하므로 벨만 포드로 문제를 해결하였습니다.

N-1번 거리에 대한 값을 갱신해주고 N번째에서 값이 또 갱신된다면 음수 사이클로 확인하였습니다.

주의해야할 점
1. 음수 사이클이 있지만 출발도시에서 해당 음수 사이클이 있는 도시에 가지 않는 경우
2. A도시에서 B도시까지 가는 경로가 여러개일 때 최소값으로 갱신

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAX_VALUE 987654321
using namespace std;

int main(int argc, char *argv[])
{
	int n, m;
	int a, b, c;
	int num;
	int check_cycle;
	vector<vector<int> > distance;
	vector<long long> value(510, MAX_VALUE);
	
	cin >> n >> m;
	
	distance.resize(n+1, vector<int>(n+1, MAX_VALUE));
	
	value[1] = 0;
	for(int i=0; i<m; ++i){
		cin >> a >> b >> c;	
		distance[a][b] = min(distance[a][b], c);
	}
	
	for(int i=1; i<=n; ++i){
		check_cycle = false;
		for(int j=1; j<=n; ++j){
			for(int k=0; k<=distance[j].size(); ++k){
				if(value[j] != MAX_VALUE && value[k] > value[j]+distance[j][k]){
					value[k] = value[j]+distance[j][k]; 	
					check_cycle = true;	
				}				
			}
		}
		if(i==1 && !check_cycle){
			break;
		}
	}
	
	if(check_cycle){
		cout << "-1" << endl;	
	} else {
		for(int i=2; i<=n; ++i){
			if(value[i] == MAX_VALUE){
				cout << "-1" << endl;	
			} else {
				cout << value[i] << endl;	
			}
		}
	}
	
	return 0;
}