글 읽기 - 다익스트라 아주 기본적인 질문 부탁드립니다.

jyheo98 3년 전 0

다익스트라에서 priority_queue의 비위를 맞춰주기 위해서 음수로 distance를 넘겨주는게 마음에 안들어서

위에 struct cmp {
bool operator() (PII a, PII b)
{
return a.ff < b.ff;
}
};

를 추가하고

priority_queue,<PII, vector<PII>, cmp> pq;

이렇게 정의했습니다.

그런데 음수로 할때는 잘 되는데 이렇게 하면 시간초과가 납니다. 혹시 이유를 알려주실 수 있나요?

참고 문서는 : https://stackoverflow.com/questions/20826078/priority-queue-comparison

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>
#include <functional>

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define MOD 1000000007LL
#define rep(i,a,n) for (int i=a ; i<n ; i++)
#define per(i,a,n) for (int i=n-1 ; i>=a ; i--)
#define LLINF (llong)1e18+5
#define INF 1e9+5

using namespace std;
using llong = long long;
using VI = vector<int>;
using VLL = vector<long long>;
using PII = pair<int, int>;

struct cmp {
	bool operator() (PII a, PII b)
	{
		return a.ff < b.ff;
	}
};
int main()
{
	IOS;

	int v, e;
	cin >> v >> e;
	int start;
	cin >> start;
	start--;
	vector<vector<PII>> f(v);
	rep(i, 0, e)
	{
		int a, b, w;
		cin >> a >> b >> w;
		a--; b--;
		f[a].push_back({ b,w });
	}
	priority_queue<PII, vector<PII>, cmp> pq;
	VI dis(v, INF);

	dis[start] = 0;
	pq.push({ 0, start });
	while (!pq.empty())
	{
		int cur = pq.top().ss;
		int curDis = pq.top().ff;
		pq.pop();
		if (curDis > dis[cur]) continue;
		rep(i, 0, f[cur].size())
		{
			int next = f[cur][i].ff;
			int nextDis = f[cur][i].ss + curDis;
			if (nextDis < dis[next])
			{
				dis[next] = nextDis;
				pq.push({ nextDis, next });
			}
		}
	}
	rep(i, 0, v)
		if (dis[i] == INF) cout << "INF " << endl;
		else cout << dis[i] << endl;

	return 0;
}

djm03178 3년 전 1

priority_queue는 원소가 큰 순서대로 뽑기 때문에 저렇게 구현할 경우 거리가 더 먼 원소를 먼저 뽑게 됩니다. 부등호 방향이 반대가 되어야 합니다.

jyheo98 3년 전 0

정말 감사합니다!

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

문제

문제

출처

ICPC

다익스트라 아주 기본적인 질문 부탁드립니다.

jyheo98 3년 전 0

djm03178 3년 전 1

jyheo98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말