글 읽기 - 시간을 더 단축하고 싶은데 어떻게 하면 좋을까요?

juhongkim2 6년 전 0

2초짜리 1400ms대로 통과해봐야 뭔가 찝찝함을 떨쳐낼 수가 없습니다...

dist[i][j] : S에서 j개 도로를 거쳐 i번 으로 가는 최단경로의 길이로 놓고 풀었습니다.

어디에서 더 줄일 수 있을까요?

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 1000000000
using namespace std;

typedef struct{
	int to,cost;
}Edge;

typedef struct{
	int node,dist,num;
}Node;

bool operator<(Node n1, Node n2)
{
	if(n1.dist>n2.dist)
		return true;

	return false;
}

int N,M,K,S,D,dist[1001][1001];
vector<Edge> g[1001];
priority_queue<Node> pq;

void Dijkstra(int start)
{
	int i,j,next;
	Node in,out;

	for(i=1;i<=N;i++){
		for(j=0;j<N;j++){
			dist[i][j]=INF;
		}
	}
	dist[start][0]=0;

	in.node=start;
	in.dist=dist[start][0];
	in.num=0;
	pq.push(in);

	while(!pq.empty()){
		out=pq.top();
		pq.pop();

		for(i=0;i<g[out.node].size();i++){
			next=g[out.node][i].to;

			if(dist[next][out.num+1]>dist[out.node][out.num]+g[out.node][i].cost){
				dist[next][out.num+1]=dist[out.node][out.num]+g[out.node][i].cost;
				in.node=next;
				in.dist=dist[next][out.num+1];
				in.num=out.num+1;
				pq.push(in);
			}
		}
	}
}

int main()
{
	int i,j,a,b,w,p,tmp,min,num;
	Edge in;

	scanf("%d %d %d %d %d",&N, &M, &K, &S, &D);

	for(i=0;i<M;i++){
		scanf("%d %d %d",&a, &b, &w);

		in.to=b;
		in.cost=w;
		g[a].push_back(in);
		in.to=a;
		in.cost=w;
		g[b].push_back(in);
	}

	Dijkstra(S);

	min=INF;
	num=-1;
	for(i=0;i<N;i++){
		if(min>dist[D][i]){
			min=dist[D][i];
			num=i;
		}
	}
	printf("%d\n",min);

	tmp=0;
	for(i=0;i<K;i++){
		scanf("%d",&p);
		min=INF;
		tmp+=p;
		for(j=num;j>=0;j--){
			if(min>dist[D][j]+j*tmp){
				min=dist[D][j]+j*tmp;
				num=j;
			}
		}
		printf("%d\n",min);
	}

	return 0;
}

jwvg0425 6년 전 2

맞은 사람 목록에서 해당 문제를 푼 다른 사람의 코드를 볼 수 있습니당(알고 계실 수도 있지만)

다른 분들 코드를 참고해보면 풀이의 어떤 부분이 달라서 속도 차이가 났는지 알 수 있지 않을까요?

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

문제

문제

출처

ICPC

시간을 더 단축하고 싶은데 어떻게 하면 좋을까요?

juhongkim2 6년 전 0

jwvg0425 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말