11657 - 타임머신

가중치에 음수가 있으므로 다익스트라가 아닌 벨만포드 알고리즘을 써야 한다.

-10000 <=C <= 10000 을 0<=C<=20000으로 바꿔서 다익스트라를 적용하려 했지만 틀렸습니다가 뜬다.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int n, m;
struct point{
	int now;
	int next;
	int cost;
};
vector<point> group;
int dist[501];
const int INF = 0x1fffffff;
int main(){
	cin >> n; cin >> m;
	group.resize(m);
	for (int i = 0; i < m; i++){
		cin >> group[i].now;
		cin >> group[i].next;
		cin >> group[i].cost;
	}
	for (int i = 1; i <= n; i++){
		dist[i] = INF;
	}
	dist[1] = 0;
	bool negative = false;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < m; j++){
			int now = group[j].now;
			int next = group[j].next;
			int cost = group[j].cost;
			if (dist[now] != INF && dist[next] > dist[now] + cost){
				dist[next] = dist[now] + cost;
				if (i == n){
					negative = true;
				}
			}
		}
	}
	if (negative){
		printf("-1");
	}
	else{
		for (int i = 2; i <= n; i++){
            if(dist[i]==INF) printf("-1\n");
			else printf("%d\n", dist[i]);
		}
	}
}