글 읽기 - 삼각 그래프 시간초과....

kkd927 8년 전 0

DP(BFS+메모제이션)로 풀었는데도 시간초과가 뜨네요...

어느 부분을 더 최적화 시켜야되는지 몰라서 질문드립니다.ㅠㅠ

/*
 * 4883번 삼각 그래프
 * https://www.acmicpc.net/problem/4883
 *
 * ID: kkd927
 * Github: https://github.com/kkd927/baekjoon
 */

#include <stdio.h>
#include <queue>
#define M 100100
#define INIT 987654321

int K;
int arr[M][4], result[M][4];
int dir[4][2] = { { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 } };
typedef struct sNode {
	int x;
	int y;
	int sum;
} node;

int main()
{
	int index = 1;
	while (1) {
		std::queue<node> q;
		scanf("%d", &K);
		if (K == 0) break;
		for (int i = 1; i <= K; i++) result[i][1] = result[i][2] = result[i][3] = INIT;
		for (int i = 1; i <= K; i++) scanf("%d %d %d", &arr[i][1], &arr[i][2], &arr[i][3]);
		
		node start, next, current;
		start.x = 1; start.y = 2; start.sum = 0;
		q.push(start);
		while (!q.empty()) {
			current = q.front(); q.pop();
			if (result[current.x][current.y] < current.sum + arr[current.x][current.y]) continue;
			result[current.x][current.y] = current.sum + arr[current.x][current.y];
			if (current.x == K && current.y == 2) continue;
			for (int i = 0; i < 4; i++) {
				int xx = current.x + dir[i][0];
				int yy = current.y + dir[i][1];
				if (xx >= 1 && xx <= K && yy >= 1 && yy <= 3) {
					next.x = xx; next.y = yy; next.sum = result[current.x][current.y];
					q.push(next);
				}
			}
		}
		printf("%d. %d\n", index++, result[K][2]);
	}
	return 0;
}

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

문제

문제

출처

ICPC

삼각 그래프 시간초과....

kkd927 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말