글 읽기 - 1753번 런타임에러...?

meme0724 9년 전 0

비주얼 스투디오에서는 제대로 실행이 되는데

여기서 채점을 하려고 하면은 런타임 에러가 뜨네요

무슨 문제가 있는건가요?

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int v, e;
vector< pair<int, int> > road;
vector<int> cost;
int dis[20001] = { 0, };
int chk[20001] = { 0, };
void dij(int k, int v)
{
	int i, s;
	pair<int, int> big;
	for (i = 0; i < 20001; i++)
	{
		dis[i] = 200000000;
	}
	
	dis[k] = 0; s = k; chk[k] = 1;

	while (s != v)
	{
		big.first = 200000000;
		chk[s] = 1;
		for (i = 1; i <= v; i++)
		{
			if (road[i].first == s)
			{
				if (chk[road[i].second] == 0 && dis[s] + cost[i] < dis[road[i].second])
				{
					dis[road[i].second] = dis[s] + cost[i];
				}
			}
		}
		for (i = 1; i <= v; i++)
		{
			if (chk[i] == 0 && big.first >= dis[i])
			{
				big.first = dis[i];
				big.second = i;
			}
		}
		s = big.second;
	}
}
int main()
{
	int k, a, b, c, i, j;

	scanf("%d %d %d", &v, &e, &k);
	road.push_back( make_pair(0, 0) );
	cost.push_back(0);
	for (i = 1; i <= e; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		road.push_back(make_pair(a, b));
		cost.push_back(c);
	}
	dij(k, e);
	
	for (i = 1; i <= v; i++)
	{
		if (dis[i] >= 200000000)
			printf("INF\n");
		else
			printf("%d\n", dis[i]);
	}
	return 0;
}

pichulia 9년 전 0

일단 런타임 에러가 발생한 원인은 배열 인덱스 초과때문입니다.

지금 보시면 chk배열을 chk[20001] 으로 잡았는데 20000보다 더 큰 i로 chk[i]를 접근하려 하고있습니다.

어디서 일까요?

for (i = 1; i <= v; i++)

{

if (chk[i] == 0 && big.first >= dis[i])

{

big.first = dis[i];

big.second = i;

}

}

이 부분인데요..

엥? 1≤V≤20,000 니까 안전범위 아니냐고요?

저 for문의 v값이 어디서 왔는지를 추적해봅시다

void dij(int k, int v)

이렇게 dij 함수 인자로 v를 사용하고 있는데

int main()

{

...

dij(k, e);

...

return 0;

}

main 함수에서 저 v에 대응하는 값으로 e를 넘겨주고 있습니다.

e값의 범위는 1≤E≤300,000 이므로

dij 함수에서 사용하는 v변수의 값의 범위도 1≤v≤300,000 이고,

따라서 i가 300,000까지 커질 수 있게 됩니다....ㄷㄷ

그러니 일단

void dij(int k) 로 바꾸고,

while문 안의 첫번째 for문을 i=1 ~ e 로 바꿔봅시다.

그럼 안정적으로 시간초과를 받으실 수 있답니다. (???)

어디가 또 문제인지는....음...일단 힌트를 드리면

while(s != v) 아래로 한 3줄 정도를 고칠 필요가 있네요

pichulia 9년 전 0

이런... 한두줄 정도 바꾸는걸로는 시간초과가 해결되지 않네요...

O((V+E)logV) 짜리 다익스트라 알고리즘에 대해 공부해봅시다.

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