글 읽기 - 오민식의 고민.. 음수 사이클에 대해 궁금한 것이 있습니다.

cprayer 7년 전 0

음수 사이클이 존재하면, 해당 음수 사이클에서 도달 가능한 모든 정점들이 계속 relaxation이 이루어지므로

이를 이용하여 음수 사이클에서 도착 정점으로 도달 가능한지 여부를 판단하려 했습니다.

구현은 처음에 SPFA를 통해 V - 1번 relaxation하여 시작 정점 S에서 도달 가능한 모든 정점을 구한 뒤,

S에서 임의의 음수 사이클 정점 A로 가는 것이 가능하고, 음수 사이클의 임의의 정점에서 도착 정점 E로 가는 경로가 존재한다면 relaxation하는

과정에서 최대 V - 1번 이내에 dist[E]가 다시 갱신된다고 가정하고 다시 한번 SPFA를 돌렸습니다.

이렇게 하니 정답이 나오질 않네요..

65번 줄이 해당 부분인데, 이 부분을 floyd나 dfs로 바꿔 음수 사이클의 임의 정점에서 E로 도달이 가능한지 여부로 바꾸면 정답이 나옵니다.

제 생각에는 이렇게 구현해도 되야 될 듯 싶은데 제가 잘못 구현한건지 가정을 잘못한건지 답이 나오지 않습니다.

고수분님들의 조언이 필요합니다!

#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

const long long INF = 1LL << 60;

int main() {
	int N, S, E, M;
	vector<pair<int, long long>> adj[101];
	scanf("%d%d%d%d", &N, &S, &E, &M);
	for (int i = 0; i < M; i++) {
		int A, B;
		long long C;
		scanf("%d%d%lld", &A, &B, &C);
		adj[A].push_back({ B, C });
	}
	long long profit[101], dist[101];
	bool visited[101], f = false;
	for (int i = 0; i < N; i++) scanf("%lld", &profit[i]);
	fill(dist, dist + N + 1, INF);
	fill(visited, visited + N + 1, false);
	dist[S] = -profit[S];
	visited[S] = true;
	queue<int> q;
	q.push(S);
	for (int i = 0; i < N - 1; i++) {
		int s = q.size();
		if (!s) break;
		for (int j = 0; j < s; j++) {
			int t = q.front(); q.pop();
			visited[t] = false;
			for (auto &l : adj[t]) {
				int B = l.first;
				long long C = l.second - profit[B];
				if (dist[B] > dist[t] + C) {
					dist[B] = dist[t] + C;
					visited[B] = true;
					q.push(B);
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		int s = q.size();
        if (!s) break;
		for (int j = 0; j < s; j++) {
			int t = q.front(); q.pop();
			visited[t] = false;
			for (auto &l : adj[t]) {
				int B = l.first;
				long long C = l.second - profit[B];
				if (dist[B] > dist[t] + C) {
					if (B == E) f = true;
					dist[B] = dist[t] + C;
					visited[B] = true;
					q.push(B);
				}
			}
		}
	}
	if (dist[E] == INF) printf("gg");
	else {
		if (f) printf("Gee");
		else printf("%lld", -dist[E]);
	}
}

dlwodnsdl 7년 전 3

V-1번만에 dist[E]가 갱신되지 않습니다.

3 0 2 4
0 1 9999
1 2 9999
1 1 9999
0 2 0
10000 10000 10000

cprayer 7년 전 0

덕분에 해결하였습니다. 애당초 가정 자체가 말이 안되는거였네요.. 왜 음수 사이클이 존재하면 바로 갱신될거라 생각했는지.. 감사합니다!

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