글 읽기 - 11657 타임머신 - 출력초과가 뜹니다. (질문검색 게시판 참고했음에도..)

shin0343 4년 전 0

벨만포드 알고리즘 사용했고, 출력초과는 질문검색을 참고하여, 입력받은 동일한 구간의 간선의 가중치는 항상 최소로 받도록 하였습니다.. 도대체 어디가 문제일까요??

구종만님의 알고리즘 책으로 벨만포드 알고리즘 공부하다가, 연습할겸 문제를 풀다 시련에 부딪혀버렸네요..ㅎㅎ

// BOJ 11657

#include <iostream>
#include <vector>
using namespace std;

#define V_MAX 502
#define INF 200000000

int ans, N, M;
vector<pair<int, int> > adj[V_MAX];

void printAns(vector<int> ansArr, bool isMinusCycle,int start)
{
	if (isMinusCycle)
	{
		cout << "-1\n";
	}
	else
	{
		int ansSize = ansArr.size();
		for (int i = start+1; i <=N; i++)
		{
			if (ansArr[i] == INF)
			{
				cout << "-1\n";
			}
			else
			{
				cout << ansArr[i] << "\n";
			}
		}
	}
}

void bellmanFord(int start)
{
	vector<int> upper(N+1, INF);
	bool updated = false;

	upper[start] = 0;

	for (int iter = 0; iter <= N; iter++)
	{
		updated = false;
		for (int here = 1; here <= N; here++)
		{
			if (upper[here] == INF) continue;

			int hereLinks = adj[here].size();
			for (int i = 0; i < hereLinks; i++)
			{
				int there = adj[here][i].first;
				int thereCost = adj[here][i].second;

				if (upper[there] > upper[here] + thereCost)
				{
					upper[there] = upper[here] + thereCost;
					updated = true;
				}
			}

			if (!updated) break;
		}
	}

	printAns(upper, updated, start);
}

int main()
{
	cin.tie(0);
	std::ios::sync_with_stdio(false);

	cin >> N >> M;

	bool isBExisted;
	int A, B, C;
	for (int i = 0; i < M; i++)
	{
		isBExisted = false;
		cin >> A >> B >> C;
		for (int i = 0; i < adj[A].size(); i++)
		{
			if (adj[A][i].first == B)
			{
				isBExisted = true;
				if (adj[A][i].second > C)
				{
					adj[A][i].second = C;
				}
			}
			if (isBExisted) break;
		}

		if (!isBExisted)
		{
			adj[A].push_back({ B,C });
		}
	}

	bellmanFord(1);

	return 0;
}

jsy8481 4년 전 1

혹시나 참고가 되실까봐 댓글을 남겨요! 저는 참고로 파이썬으로 해서 위 코드를 잘 모르겠어요

출력 초과가 떠서 저는 입력을 수정하여서 해결했습니다.

입력으로 인해 출력 초과가 되는 것은 -100 엣지랑 1 엣지랑 동일 구간에 있을 때 1->2로 만약 -100 엣지를 입력 받으면 1->2 2->1 음의 사이클이 생겨서 -1을 출력하야 하나 / 1인 엣지가 이를 덮어 씌운다면 음의 싸이클이 사라질 수 있다!

이런 식으로 이해했어요 -> 음의 싸이클이 있으면 -1 을 출력해야 하지만 노드까지의 거리를 출력하기 때문에(노드 수 만큼 출력) 출력 초과가 발생하는 것 같구요

입력도 수정하셨다면 혹시나 출력 초과의 원인은 음의 싸이클이 있지만 이를 인식하지 못하고 노드 까지의 거리를 출력하고 있지 않나 생각합니다.

주저리주저리 쓴 점 양해부탁드립니다. 도움이 되었으면 좋겠습니다.

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