글 읽기 - 어떻게해야 시간을 줄일 수 있을까요?

yyoouunngg 4년 전 0

안녕하세요...! 시간초과가 계속 떠서 잠을 못자겠씁니다... 풀어야 잘 수 있을 것 같습니다. 제발 도와주세요...ㅜㅜㅜ

어떤 방식을 취해야 시간이 줄어들 수 있나요?

#include <bits/stdc++.h>
using namespace std;

struct node
{
	int weight, x, y;
};
bool operator< (node a, node b)
{
	return a.weight < b.weight;
}

const int inf = 987654321;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

int main()
{
	int i = 1;
	int n;
	while (1)
	{
		int n;
		scanf("%d", &n);
		if (!n)return 0;
		int arr[130][130];
		int res[130][130];
		memset(arr, 0, sizeof(arr));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				scanf("%d",&arr[i][j]);
				res[i][j] = inf;
			}
		}
		priority_queue<node> q; // 가중치, x, y
		q.push({ arr[0][0],0,0 });
		res[0][0] = arr[0][0];
		while (q.size())
		{
			int curx = q.top().x;
			int cury = q.top().y;
			int curw = q.top().weight;
			q.pop();
			for (int i = 0; i < 4; i++)
			{
				int nx = curx + dx[i];
				int ny = cury + dy[i];
				int nw = curw + arr[ny][nx];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (res[ny][nx] > nw)
				{
					res[ny][nx] = nw;
					q.push({ nw,nx,ny });
				}
			}
		}
		printf("Problem %d: %d\n", i, res[n - 1][n - 1]);
		i++;
	}
}

lovinix 4년 전 0

c의 priority queue는 max heap입니다.

weight를 음수로 넣어주시거나 10번째 줄 a.weight < b.weight를 a.weight > b.weight로 고쳐주세요

yyoouunngg 4년 전 0

@lovinix 아... 기초적인걸 캐치하지 못했네요.

해결했습니다! 감사합니다 좋은하루되세요~~ㅎㅎ♥♥

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

문제

문제

출처

ICPC

어떻게해야 시간을 줄일 수 있을까요?

yyoouunngg 4년 전 0

lovinix 4년 전 0

yyoouunngg 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말