글 읽기 - 런타임에러

pmzy 6년 전 0

런타임 에러 원인을 찾을수가 없네요 도저히..

직접 돌려보면 잘돌아가는것 같은데

답답해 미치겠네요.. 도와주실분..

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector <pair<int, int>> map[1001];
int result = 0;

void input()
{
	scanf("%d%d", &n, &m);

	int a, b, t;
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &t);
		map[a].push_back(make_pair(b, t));
	}
}

int dijkstra()
{
	int cost;
	int start;
	int minimum = 987654321;
	priority_queue <pair<int, int>> q;

	q.push(make_pair(0, 1));

	while (!q.empty())
	{
		start = q.top().second;
		cost = -q.top().first;
		q.pop();

		if (start == n)
		{
			minimum = minimum < cost ? minimum : cost;
			continue;
		}

		int size = map[start].size();
		for (int i = 0; i < size; i++)
		{
			if (map[start][i].second == -1)
			{
				continue;
			}

			int cost_cur = -map[start][i].second - cost;
			int next = map[start][i].first;

			q.push(make_pair(cost_cur, next));
		}
	}

	return minimum;
}

void process()
{
	int minimum = dijkstra();

	for (int i = 1; i <= n; i++)
	{
		int size = map[i].size();
		for (int j = 0; j < size; j++)
		{
			int tmp = map[i][j].second;
			map[i][j].second = -1;

			int curvalue = dijkstra();
			int nextmin = curvalue - minimum;

			result = nextmin > result ? nextmin : result;

			map[i][j].second = tmp;
		}
	}
}

void output()
{
	if (result > 900000)
	{
		printf("-1\n");
	}
	else
	{
		printf("%d\n", result);
	}
}

int main(void)
{
	input();
	process();
	output();
	return 0;
}

yukariko 6년 전 1

다익스트라의 구현에 문제가 있네요.

정점에 대해 방문여부를 알 수 없으니 사이클이 생기면 무한루프를 돌게 될 것입니다.

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

문제

문제

출처

ICPC

런타임에러

pmzy 6년 전 0

yukariko 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말