글 읽기 - 런타임에러....

zhoang3 6년 전 0

런타임에러 설명좀 부탁드립니다...

#define N 20000
#define INF 500000

#include <iostream>
#include <string>
int inp[N + 100][N + 100] = { 0, };
bool visit[N + 100] = { 0, };
int dst[N + 100] = { 0, };

int V, E;
int K;

using namespace std;

void Input() {

	cin >> V >> E >> K;

	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++)
			if (i != j)
				inp[i][j] = INF;
	}

	while (E--) {
		int st, dt, pt;

		cin >> st >> dt >> pt;

		inp[st][dt] = pt;
	}
	
	for (int i = 1; i <= V; i++)
		dst[i] = INF;
}

void Dijk() {
	// 시작점 0
	dst[K] = 0;
	
	int v;

	for (int i = 1; i <= V; i++) {
		int min = INF;

		//K(1) 에서 2 = K(1) + a(1)(2)
		for (int j = 1; j <= V; j++) {
			if (visit[j] == false && min > dst[j]) {
				min = dst[j];
				v = j;
			}
		}

		visit[v] = true;

		for (int j = 1; j <= V; j++) {
			if (dst[j] > dst[v] + inp[v][j])
				dst[j] = dst[v] + inp[v][j];
		}
	}
	}


int main() {

	Input();

	Dijk();
	
	for (int i = 1; i <= V; i++) {
		if (dst[i] == INF) cout << "INF" << endl;
		else	cout << dst[i] << endl;
	}

	
}

chogahui05 6년 전 0

인덱스 범위를 벗어나면 런타임 에러가 뜨겠네요.

인접 리스트로 구현을 안 하고, 인접 행렬로 구현하신 거 같은데요.

정점의 갯수가 V라면, 인접 행렬로 구현하실 경우 공간 복잡도가 V^2가 되겠죠?

그런데 V = 2만이네요. 2만 * 2만 = 4억. inp 배열의 크기가 4억 * sizeof(int)네요.

64bit라 가정하면 대충 32억 byte가 되겠는데요? 런타임 에러가 안 걸려도

계산 과정에서 시간 초과 먹겠네요.

chogahui05 6년 전 0

일단 이 문제 같은 경우, 정점의 갯수는 최대 2만개고요.

path의 갯수가 최대 30만개네요.

행렬로 표현했을 때, 4억이네요. 그리고 인접 리스트로 표현한 경우, 최대 30만..

30만 / 4억 = 약 3/4000인가요?

only C로 구현하시려면 희소 행렬을 구현하셔야 합니다.

java는 Map을 써 주시면 되는데.. key값으로 무엇을 넣으면 좋을 지는 잘 생각해 보세요.

나머지 과정은, 생략하도록 할게요.

솔직히 질답게 보면 바로 나오긴 하지만, 쉽게 알려주면 넘넘 시시하잖아요.

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

문제

문제

출처

ICPC

런타임에러....

zhoang3 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말