[C++] 11657: 타임머신

골드4인가

 

#include <iostream>
#include <vector>
#define INF 50000000000
using namespace std;
int N, M;

struct edgeInfo {
	int sn;
	int en;
	long long weight;
};

vector<edgeInfo> edges;
long long dis[501];

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) dis[i] = INF;
	dis[1] = 0;

	int a, b;
	long long c;
	for (int i = 0; i < M; i++) {
		scanf("%d%d%lld", &a, &b, &c);
		edges.push_back({ a, b, c });
	}

	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M; j++) {
			edgeInfo edge = edges[j];
			if (dis[edge.sn] == INF) continue;
			long long newdis = dis[edge.sn] + edge.weight;
			if (dis[edge.en] > newdis) dis[edge.en] = newdis;
		}
	}

	bool isMinuscycle = false;
	for (int j = 0; j < M; j++) {
		edgeInfo edge = edges[j];
		if (dis[edge.sn] == INF) continue;
		long long newdis = dis[edge.sn] + edge.weight;
		if (dis[edge.en] > newdis) isMinuscycle = true;
	}
	if (isMinuscycle) {
		printf("-1\n");
		return 0;
	}
	for (int i = 2; i <= N; i++) {
		if (dis[i] == INF) printf("-1\n");
		else printf("%lld\n", dis[i]);
	}
}

 

벨만포드

 

-> 음수 가중치를 가진 간선이 존재할 때

-> 음수 사이클 여부는 union find로!

 

--> ㅇ..? union find가 어딨어? 웬? 먼소리?