글 읽기 - 시간초과 ㅜㅜ 도와주세요

iljimae 7년 전 1

시작하는 지점과 끝나는 지점을 바꿔주면서 모든 D개의 점에 대해서 다익스트라를 적용하고 답을 갱신했는데 시간초과가 나네요 (입력 사이즈를 보니 당연한 결과입니다). 어떻게 최적화를 시켜야할지 아이디어가 떠오르지 않아요 도와주세요 ㅜㅜ

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
#include <vector> 
#include <queue>  
#include <utility> 
using namespace std; 

#define INF 987654321
#define MAXR 2001 
#define MAXC 201 
typedef pair<int,int> P;  
typedef pair<int,P> PP;  // 최단거리, 위치번호  
int R,C,D;  
int G[MAXR][MAXC]; 
int d[MAXR][MAXC]; 

bool inRange(int y,int x){
	return (y >= 1 && y <= R && x >= 1 && x <= C);  
}

void dijkstra(P start){
	priority_queue< PP,vector<PP>,greater<PP> > que;  
	for (int i = 1; i <= R; i++){
		for (int j = 1; j <= C; j++){
			d[i][j] = INF;  
		}
	}
	d[start.first][start.second] = G[start.first][start.second]; 
	que.push(PP(d[start.first][start.second],start));  
	while (!que.empty()){
		PP pp = que.top(); que.pop();  
		P v = pp.second;  
		if (d[v.first][v.second] < pp.first) continue;  
		for (int i = 0; i < 4; i++){
			int nr,nc;  
			if (i == 0){ //left  
				nr = v.first;  
				nc = v.second-1;  
				if (inRange(nr,nc) && d[nr][nc] > d[v.first][v.second]+G[nr][nc]){
					d[nr][nc] = d[v.first][v.second]+G[nr][nc]; 
					que.push(PP(d[nr][nc],P(nr,nc))); 
				}
			}else if (i == 1){ // right
				nr = v.first;  
				nc = v.second+1;  
				if (inRange(nr,nc) && d[nr][nc] > d[v.first][v.second]+G[nr][nc]){
					d[nr][nc] = d[v.first][v.second]+G[nr][nc]; 
					que.push(PP(d[nr][nc],P(nr,nc))); 
				}
			}else if (i == 2){ //up 
				if (v.second != 1 && v.second != C) continue;  
				else{
					nr = v.first-1;  
					nc = v.second;  
					if (inRange(nr,nc) && d[nr][nc] > d[v.first][v.second]+G[nr][nc]){
						d[nr][nc] = d[v.first][v.second]+G[nr][nc]; 
						que.push(PP(d[nr][nc],P(nr,nc)));  
					}
				}
			}else if (i == 3){ // down 
				if (v.second != 1 && v.second != C) continue;  
				else{
					nr = v.first+1;  
					nc = v.second;  
					if (inRange(nr,nc) && d[nr][nc] > d[v.first][v.second]+G[nr][nc]){
						d[nr][nc] = d[v.first][v.second]+G[nr][nc];  
						que.push(PP(d[nr][nc],P(nr,nc))); 
					}
				}
			}
		}
	}
}

int main(){
	scanf("%d %d",&R,&C);  
	for (int i = 1; i <= R; i++){
		for (int j = 1; j <= C; j++){
			scanf("%d",&G[i][j]); 
		}
	}
	scanf("%d",&D); 
	P start = P(1,1),end;  
	dijkstra(start); 
	int ans = 0;  
	for (int i = 0; i < D; i++){
		scanf("%d %d",&end.first,&end.second);  	
		ans += d[end.first][end.second];  
		if (i != D-1){
			ans -= G[end.first][end.second]; 
			start = end;  
			dijkstra(start); 
		}  
	}
	printf("%d\n",ans);    
	return 0;  
}

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

문제

문제

출처

ICPC

시간초과 ㅜㅜ 도와주세요

iljimae 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말