글 읽기 - 어디가 틀렸는지 모르겠어요.ㅜ

na982 6년 전 1

벨만 포드에서 목적지에 연결되는 음수 사이클을 처리 하기 위해서 2 * n 만큼 반복하면서

반복문이 n - 1 이후에 목적지가 갱신되는 경우를 체크 했습니다.

if ((i >= (n - 1)) && (there == e)) {
negative_cycle = 1;
break;
}

그리고 나머지는 전형적인 벨만 포드 알고리즘을 구현했는데요; 어느 부분이 틀렸는지 잘 모르겠네요;;

고수님들 도움 부탁 드립니다.

#include <stdio.h>

#define INF (576460752303423488)

typedef struct NODE {
	int node, cost;
}_NODE;

int n, s, e, m;
int con_size[100], money[100];
_NODE con[100][100];
long long result[100];


int main()
{
	scanf("%d %d %d %d", &n, &s, &e, &m);
	int a, b, p;
	for (int i = 0; i < m; ++i) {
		scanf("%d %d %d", &a, &b, &p);
		int& size = con_size[a];
		con[a][size].node = b;
		con[a][size].cost = p;
		++size;
	}
	for (int i = 0; i < n; ++i) {
		scanf("%d", &money[i]);
	}

	for (int i = 0; i < n; ++i) {
		result[i] = -INF;
	}

	int negative_cycle = 0;
	result[s] = money[s];
	for (int i = 0; i < (2 * n) && negative_cycle == 0; ++i) {
		for (int j = 0; j < n && negative_cycle == 0; ++j) {
			int here = (j + s) % n;
			for (int k = 0; k < con_size[here]; ++k) {
				int there = con[here][k].node;
				int cost = con[here][k].cost;
				if (result[here] != -INF) {
					if (result[there] < (result[here] + money[there] - cost)) {
						result[there] = (result[here] + money[there] - cost);
						if ((i >= (n - 1)) && (there == e)) {
							negative_cycle = 1;
							break;
						}
					}
				}
			}
		}
	}

	if (negative_cycle == 1) {
		printf("Gee\n");
	} else if (result[e] == -INF) {
		printf("gg\n");
	}
	else {
		printf("%lld\n", result[e]);
	}

	return 0;
}

na982 6년 전 0

negative_cycle 을 따로 queue를 이용해서 탐색하면; ac가 뜨네요;

하지만 위의 코드 처럼 2 * n 만큼 반복해서 돌면; 처리가 될꺼라 생각했는데; 안되네요; 반례를 모르겠어요~

고수님들 답변좀 부탁 드립니다.

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠어요.ㅜ

na982 6년 전 1

na982 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말