글 읽기 - (시간초과) 나름대로 SPFA로 풀어봤는데 시간초과. 도와주세요.

wakeupear1y 6년 전 0

입력을 받을때, From 노드에 붙어있는 모든 To 노드들을 탐색할 수 있게 저장 후, InQ를 사용하여 풀어본 소스입니다.

탐색은 To 노드들의 인덱스가 저장되어있는 Prev 배열을 이용하였습니다.

하지만 제출시 시간초과가 뜨네요. InQ에 있는 노드들은 Q에 들어가지 않기 때문에 꽤 빠르게 동작할거라고 생각했는데 아닌가보네요.

어딘가 개선이 필요해보이는데, 도움이나 조언 부탁드리겠습니다.

// 간선: 300000
// 노드: 20000
#include <stdio.h>
#define MAXV 20001
#define MAXE 300001
#define INF 987654321
struct FlowInfo
{
	int from, to, weight;
};
FlowInfo Flow[MAXV];
int Prev[MAXE], To[MAXV], InQ[MAXV];
int Dist[MAXV], Q[MAXV * 100], Qidx;
int V, E, StartNode;

void init()
{
	for (int i = 0; i < MAXE; ++i) Prev[i] = -1;
	for (int i = 0; i < MAXV; ++i) { To[i] = -1, Dist[i] = INF, InQ[i] = 0; }
}
// 출력: i번째로 가는 최단 경로의 값
int main()
{
	// Prev, To 를 -1로 초기화
	init();
	scanf("%d%d%d", &V, &E, &StartNode);
	// 간선정보 입력
	for (int i = 1; i <= E; ++i) {
		scanf("%d%d%d", &Flow[i].from, &Flow[i].to, &Flow[i].weight); 
		Prev[i] = To[Flow[i].from];
		To[Flow[i].from] = i;
	}

	// 큐에 시작점 넣기
	int front = 0, rear = 1;
	Q[rear] = StartNode;

	int curNode = Q[rear];
	// 인큐
	InQ[curNode] = 1;
	// 시작점 거리는 0으로
	Dist[curNode] = 0;
	while (front < rear)
	{
		for (int idx = To[curNode]; idx != -1; idx = Prev[idx])
		{
			// to로의 최단경로 갱신, curNode에 달려있는 Node들 검사
			if (Dist[Flow[idx].to] > Dist[Flow[idx].from] + Flow[idx].weight) {
				Dist[Flow[idx].to] = Dist[Flow[idx].from] + Flow[idx].weight;
				// 인큐에 들어있지 않다면 넣어준다.
				if (InQ[idx] != 1) {
					Q[rear++] = Flow[idx].to;
					InQ[Flow[idx].to] = 1;
				}
			}
		}
		// InQ에서 pop하여 Q에 넣어줌
		InQ[curNode] = 0;
		front++;
		curNode = Q[front];
	}
	for (int i = 1; i <= V; ++i)
	{
		if (Dist[i] == INF)
			printf("INF");
		else
			printf("%d", Dist[i]);
		printf("\n");
	}
}

cheetose 6년 전 1

spfa의 worst case의 시간복잡도는 O(VE) 입니다.

Green55 6년 전 1

일단 이 문제는 SPFA를 저격하는 데이터는 없어서, SPFA로도 시간 내 충분히 통과 가능합니다.

소스에 큰 문제는 없어보이는데 MAXV * 100의 크기가 충분한지는 잘 모르겠네요.

wakeupear1y 6년 전 0

@cheetose 님
평균적으로 O(E) 만큼 도는 걸로 알고있는데, 실제 채점 데이터에 Worst Case가 들어가 있다고 봐야겠죠?

@ssangba55 님
Q의 크기를 늘려봐도 동일하게 시간초과 발생 하네요. 시간을 잡아 먹는곳이 어딜까요.

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

문제

문제

출처

ICPC

(시간초과) 나름대로 SPFA로 풀어봤는데 시간초과. 도와주세요.

wakeupear1y 6년 전 0

cheetose 6년 전 1

Green55 6년 전 1

wakeupear1y 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말