글 읽기 - 다익 질문드려요

wjdtmdrbs88 7년 전 0

다익스트라로 풀어보았습니다. 시간초과를 어떻게 줄일 수 있을까요 ?

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
int n;
int arr[126][126];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};

int main()
{
	int cnt = 0;
	while( 1 )
	{
		scanf("%d", &n);
		if(!n) break;
		for(int i = 0 ; i < n ; i++)
			for(int j = 0 ; j < n ; j ++)
				scanf("%d", &arr[i][j]);
		
		vector< vector< int > > d(n+1, vector<int>(n+1, INF));
		
		priority_queue< pair< int, pair<int, int> > > pq;
		pq.push( make_pair(arr[0][0], make_pair(0,0)));
		d[0][0] = arr[0][0];
		
		while(!pq.empty())
		{
			int y = pq.top().second.first;
			int x = pq.top().second.second;
			int dist = pq.top().first;
			pq.pop();
			
			if(y == n-1 && x == n-1)
				continue;
			
			for(int i = 0 ; i < 4; i++)
			{
				int ny = y+dy[i];
				int nx = x+dx[i];
				
				if(ny < 0 || ny > n-1 || nx < 0 || nx > n-1)
					continue;
				int cost = arr[ny][nx];
				
				if( dist + cost < d[ny][nx] )
				{
					d[ny][nx] = dist+cost;
					pq.push(make_pair(d[ny][nx], make_pair(ny,nx)));
				}
			}
		}
		
		printf("problem %d: %d\n", ++cnt, d[n-1][n-1]);
	}
}

haja 7년 전 0

priority_queue가 기본적으로 맥스힙이라 민힙으로 바꿔주셔야 할 것 같구요. 이미 방문한 노드일 경우, 안쪽 for문이 돌지 않게 하시면 될 것 같아요.

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

문제

문제

출처

ICPC

다익 질문드려요

wjdtmdrbs88 7년 전 0

haja 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말