글 읽기 - 최단경로

dkfwl24 7년 전 0

소스코드 줄이고 줄였는데 계속 시간초과가 나네요..

무엇이 문제일까요?

 #include <iostream>
#include <queue>

using namespace std;

int v, e, k;
vector<pair<int, int>> adj[20001];
int f_min(int a, int b);    //최소값구하는함수
int f_cost(int mid, int i); //mid노드에서 i노드로 가는 거리

int main(){
	 ios::sync_with_stdio(false);
	//////////////////
	//초기화 및 입력//
	//////////////////

	scanf("%d", &v);
	scanf("%d", &e);
	scanf("%d", &k);

	for(int i=1; i<=e; i++){
		int a, b, c;
		scanf("%d", &a);
		scanf("%d", &b);
		scanf("%d", &c);
		adj[a].push_back(make_pair(b, c));
	}

	vector<int> dist(v+1, 99);
	vector<int> S(v+1, 0);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

	dist[k] = 0;
	int mid = k;
	q.push(make_pair(k, 0));

	/////////////////
	//알고리즘 시작//
	/////////////////
	
	while(!q.empty()){
		mid = q.top().first;
		S[mid] = 1;

		while(!q.empty()){			
			q.pop();
		}

		for(int i=1; i<=v; i++){
			if(S[i] != 1){
				dist[i] = f_min(dist[i], dist[mid] + f_cost(mid, i));
				q.push(make_pair(i, dist[i]));
			}
		}
	}//while
	
    ///////
	//출력//
	///////
    
	for(int i=1; i<=v; i++){
		if(dist[i] == 99) printf("INF\n");
		else printf("%d\n", dist[i]);
	}

	return 0;
}

int f_min(int a, int b)
{
	if(a > b) return b;
	else return a;
}

int f_cost(int mid, int i)
{
	if(adj[mid].empty()) return 99;

	for(int j=0; j<adj[mid].size(); j++){
		if(adj[mid][j].first == i) return adj[mid][j].second;
	}

	return 99;
}

hoon222y 7년 전 0

priority queue로 구현하는 이유가 top을 이용해서 가중치가 가장 작은 경우를 뽑고싶은것인데 지금 큐에 들어갈 떄 그냥 dist로 들어가서 top에서 원하는 값을 뽑아내지 못하는거 같습니다.

dist를 음수로 넣어 top에서 가중치가 가장 작은 지점을 뽑을수 있도록 해보시면 될 것 같습니다.

ehddml3 7년 전 0

음.. 다익스트라 or dijkstra로 검색한번 해보셔서 알고리즘을 제대로 봐보는게 좋을 듯 하네용

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

문제

문제

출처

ICPC

최단경로 - 시간초과

dkfwl24 7년 전 0

hoon222y 7년 전 0

ehddml3 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말