글 읽기 - KCM travel 다익스트라 코드, 속도 개선 방법 부탁드립니다ㅠㅠ

imno1234 5년 전 0

다익스트라를 이용하여 KCM travel 을 풀었고 AC를 받았습니다.

하지만 다른분들의 코드 및 결과를 보니 크게 바텀업 DP를 이용한 풀이와 다익스트라를 이용한 풀이가 있는데, 같은 다익스트라풀이임에도 제 코드는 지나치게 느린것 같습니다.

if 문 조건으로 건너뛰는 대신 continue를 사용해보거나, Q.top()을 트리플렛 데이터로 받고 각각의 변수를 설정하냐 아니면 각 변수를 계속 Q.top()의 first/second로 접근해서 받냐 등
사소한, 이런저런 개선을 시도해봤지만, 잘 안 돼서 질문드립니다.

아래의 코드에서 어떤 부분이 시간을 많이 잡아먹는건지, 이런 문제를 풀때 어떻게 하면 빠른 코드를 만들 수 있는지 궁금합니다.

감사합니다!

#include<cstdio>
#include<vector>
#include<queue>
#define B 1000000000//Big num
using namespace std;
typedef pair<int,int>I;
typedef pair<int,I>J;
typedef vector<J>W;
typedef vector<int>V;
priority_queue<J>Q;//트리플렛정보를 받는 우선순위 큐, Q
int main(){
	int i,T,N,M,K,u,v,c,d,U,C,D,m;
	for(scanf("%d",&T);T--;){
        m=B;//n까지 도착하는 거리의 min값 매 TC마다 초기화
		vector<W>A;//트리플렛저장을 위한 벡터 W의 벡터(배열)
        Q.push({0,{1,0}});
		for(scanf("%d%d%d",&N,&M,&K),A.assign(N+1,W());K--;A[u].push_back({v,{c,d}}))scanf("%d%d%d%d",&u,&v,&c,&d);
        //이상 vector에 pair로 입력 받기
		vector<V>R(N+1,V(10001,B));R[1][0]=0;//R[u][i]=정점u에 i만큼의 비용으로 도착하는 최단거리
		while(!Q.empty()){//priority queue를 이용한 다익스트라 알고리즘. 우선순위를 뒤집기 위해 거리값에 -곱하여 큐에 저장.
			D=-Q.top().first;U=Q.top().second.first;C=Q.top().second.second;Q.pop();
			if(D<=R[U][C]&&U!=N)for(i=A[U].size();i--;){
				v=A[U][i].first;c=A[U][i].second.first+C;d=A[U][i].second.second+D;
				if(c<=M&&d<R[v][c]){R[v][c]=d;Q.push({-d,{v,c}});}
			}
		}
		for(i=M+1;i--;)m=m>R[N][i]?R[N][i]:m;//R[N]중에 가장 빠른 거리 찾아 출력
		printf(m-B?"%d\n":"Poor KCM\n",m);
	}
}

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

문제

문제

출처

ICPC

KCM travel 다익스트라 코드, 속도 개선 방법 부탁드립니다ㅠㅠ

imno1234 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말