글 읽기 - 음수 사이클 판명

maro7913 4년 전 0

음수 사이클 판명 할 떄 꼭

N-1번 돌려야 하는 이유가 있나요?

한번 다 돌리고 한번 더 돌려봤을 떄 변화가 있으면 안되나요?

#include<iostream>
#include<vector>
const int INF = 0x7FFFFFFF;
using namespace std;

int main() {
	int N, M, A, B, C;
	cin >> N >> M;
	vector<vector<int>> city(N + 1, vector<int>(N + 1, INF));
	vector<int> dist(N + 1, INF);
	while (M--) {
		cin >> A >> B >> C;
		if (city[A][B] == INF) {
			city[A][B] = C;
		}
		else {
			if (city[A][B] > C) {
				city[A][B] = C;
			}
		}
	}
	dist[1] = 0;
	for (int s = 1; s <= N; s++) {//Find way
		for (int d = 1; d <= N; d++) {
			if (s != d && dist[s] != INF &&city[s][d]!=INF) {//s!=d because it mean goes itself
				if (dist[d] > dist[s] + city[s][d]) {
					dist[d] = dist[s] + city[s][d];
				}
			}
		}
	}
	for (int s = 1; s <= N; s++) {//check loop
		for (int d = 1; d <= N; d++) {
			if (s != d && dist[s] != INF && city[s][d] != INF) {//s!=d because it mean goes itself
				if (dist[d] > dist[s] + city[s][d]) {
					cout << -1 << endl;
					return 0;
				}
			}
		}
	}

	for (int i = 2; i <= N; i++) {
		if (dist[i] == INF) cout << -1 << endl;
		else cout << dist[i] << endl;
	}
	return 0;
}

pichulia 4년 전 1

최단경로는 많아봤자 최대 N개의 정점을 가질테고, 따라서 가능한 경로는 최대 N-1개의 간선으로 이루어져 있습니다.

따라서 만약 N-1번 루프를 돌았는데 아직도 최단경로가 갱신이 된다면, 그건 음수사이클이 있다는 얘기가 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

음수 사이클 판명

maro7913 4년 전 0

pichulia 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말