글 읽기 - 16681 등산 시간초과 뜹니다.

dlswmd08 5년 전 0

실력이 부족해서 어떤 반복문을 없에야 복잡도를 줄일 수 있는지 모르겟네요 ..ㅠ

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>

using namespace std;
const int P_INF = 1000000;
typedef pair<int, int> P;


int main()
{
	int N, M, D, E;
	scanf("%d %d %d %d", &N, &M, &D, &E);
	
	int height[N];
	
	for(int i=0; i < N; i++){
		scanf("%d", &height[i]);
	}
	
	vector<P> adj[N];
	
	for(int i=0; i < M; i++){
		int u, v, k;
		scanf("%d%d%d", &u, &v, &k);
		adj[u-1].push_back(P(k,v-1));
		adj[v-1].push_back(P(k,u-1));
	}
	
	priority_queue<int, vector<int>, less<int> > PQ;
	bool path=0;
	for(int i=1; i < N - 1; i++){
		priority_queue<P, vector<P>, greater<P> > QN;

		bool visited[N];
		memset(visited, 0, sizeof(visited));
		int value [N];
		fill(value, value+N, P_INF);
		value[i] = 0;
		QN.push(P(0,i));
		
		while(!QN.empty()){
			int curr;
			int cost;
			
			do{
				curr = QN.top().second;
				cost = QN.top().first;
				QN.pop();
			}while(!QN.empty() && visited[curr]);
			
			if(visited[curr]) break;
			
			visited[curr] = true;
			
			for(auto &p : adj[curr]){
				int dist = p.first, next = p.second;
				
				if(height[next] >= height[curr]) continue;
				
				int tmp = dist;
				if(value[next] > cost + tmp){
					value[next] = cost + tmp;
					QN.push(P(value[next],next));
				}
			} 	
		}
		
		int up = value[0];
		int down = value[N-1];
		
		if( up != P_INF && down != P_INF ){
			path++;
			PQ.push( E*height[i] - D*(up+down));
		}
	}
	
	if(path){
		printf("%d\n", PQ.top());
	}else{
		printf("Impossible\n");
	}
	
}

hello70825 5년 전 0

최악의 경우 100,000개의 지점이 값으로 들어오는데, 위 코드에 그런 값이 들어오면 99,998번의 다익스트라를 해야합니다. 시간이 오래 걸리겠죠?

더 간단한 풀이를 생각해보시는 것을 추천 드립니다.

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

문제

문제

출처

ICPC

16681 등산 시간초과 뜹니다.

dlswmd08 5년 전 0

hello70825 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말