글 읽기 - 1753 최단경로 65%에서 런타임 에러가 발생합니다.

conatus_recedendi 3년 전 0

* 아래 코드에서 int w는 사용하지 않습니다.

* 38번째줄의 l[x][1] >= 0 을 확인하는 부분도 사용하지 않습니다.

게시글에 올라온 다른 반례들과 테스트를 65%까지 통과한 것으로 보아
특수한 경우 혹은 데이터가 커질 때 런타임 에러가 발생하는 것으로 보입니다.

어떤 부분에서 오류가 발생하는 것일까요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<pair<int, int> > list[20005];
priority_queue<pair<int, int> > pq;
int		l[20005][2];
int main(void)
{
	int v, e, k, a, b, c;
	cin >> v >> e >> k;
	int i = 0;
	while (i < e)
	{
		cin >> a >> b >> c;
		list[a].push_back(pair<int, int>(b, c));
		i++;
	}
	i = 1;
	while (i <= v)
	{
		l[i][0] = 0x7fffffff;
		i++;
	}
	l[k][0] = 0;
	pq.push(pair<int, int>(0, k));
	while (!pq.empty())
	{
		int w = -pq.top().first;
		int s = pq.top().second;
		pq.pop();
		i = 0;
		while (i < list[s].size())
		{
			if (l[list[s].at(i).first][1] >= 0)
			{
				if (l[list[s].at(i).first][0] > l[s][0] + list[s].at(i).second)
				{
					l[list[s].at(i).first][0] = l[s][0] + list[s].at(i).second;
					pq.push(pair<int, int>(-l[list[s].at(i).first][0], list[s].at(i).first));
				}
				l[i][1] = 1;
			}
			i++;
		}
	}
	i = 1;
	while (i <= v)
	{
		if (l[i][0] == 0x7fffffff)
			cout << "INF\n";
		else
			cout << l[i][0] << "\n";
		i++;
	}
}

seico75 3년 전 1

어짜피 안쓰는 코드라고하셨는데... 45라인이 문제인 것 같습니다.

l의 첫인자로 i 는 안맞는 것 같네요.

0이서 시작하고 0에서 1로 가는 경로가 20'005 개 이상이면 메모리 침범으로 문제가 생길 것 같네요.

conatus_recedendi 3년 전 0

네 그 부분이 틀렸던거네요 ㅠㅠ

정점의 개수가 2만개 이하라 한 정점의 간선 최대도 2만개 이하일거라 생각했던게 원인이였네요.

감사합니다!

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

문제

문제

출처

ICPC

1753 최단경로 65%에서 런타임 에러가 발생합니다.

conatus_recedendi 3년 전 0

seico75 3년 전 1

conatus_recedendi 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말