글 읽기 - priority queue 설정 질문입니다.

kkw564 6년 전 1

우선순위 큐를 priority_queue<pii, vector<pii>, greater<pii>> pq; 이렇게 잡으니 시간 초과이고

priority_queue<int> pq 이렇게 잡고 -로 가중치를 주니 통과네요

많은 차이가 나는것인가요?

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <cstdio>
#include <functional>

#define max(a,b)(a > b ? a : b)

using namespace std;

typedef pair<int, int> pii;

vector<pii> adj[1001];

vector<int> dijkstra(int src, int V, int E)
{
	// 정점 개수만큼 INT_MAX로 초기화
	vector<int> dist(V, INT_MAX);
	dist[src] = 0; // 자기 자신 최단거리는 0

	priority_queue<pii, vector<pii>, greater<pii>> pq;

	pq.push(pii(src, 0));

	while (!pq.empty())
	{
		// cost :: 현재 정점까지 최단 거리
		int here = pq.top().first;
		int cost = pq.top().second;

		pq.pop();

		// dist :: 현재 정점이 가지고 있던 최단 거리
		// 현재 정점이 가지고 있던 최단 거리가 
		if (dist[here] < cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].first;
			// thereDist :: 현재 정점에서 가중치를 더한 거리
			int thereDist = adj[here][i].second + cost;

			// 현재 정점이 가지고 있던 최단거리가 현재 정점에서 가중치를 더한 거리보다 크면 바꾼다.
			if (dist[there] > thereDist)
			{
				dist[there] = thereDist;
				pq.push(pii(there, thereDist));
			}
		}
	}

	return dist;
}

int main()
{
	// 정점, 간선의 개수 및 도착점
	int V, E, end;

	scanf("%d %d %d", &V, &E, &end);

	V++; // 정점의 개수가 1부터 시작하면 V++해준다.

	for (int i = 0; i < E; i++)
	{
		int from, to, val;
		scanf("%d %d %d", &from, &to, &val);

		adj[from].push_back(pii(to, val));
	}

	int ans = 0;
	for (int start = 1; start < V; start++)
	{
		vector<int> go = dijkstra(start, V, E);
		vector<int> come = dijkstra(end, V, E);

		ans = max(ans, go[end] + come[start]);
	}

	printf("%d", ans);

	return 0;
}

kkw564 6년 전 0

가독성을 위해 greater<int>가 좋은건가요 아니면 -로 가중치를 두는 것이 좋은건가요?

ntopia 6년 전 0

pair 끼리 비교할 때는

first 를 먼저 비교하고, first가 같으면 second를 비교합니다

저 위의 소스에서는 first에 정점 번호를, second에 거리를 넣고 있는데

이러면 pq.top() 의 값은 거리가 가장 짧은게 이니라 "정점번호가 가장 작은 것" 이 나오겠죠.

따라서 다익스트라 알고리즘이라고 할 수 없기 때문에 TLE가 나는 것 같네요

first랑 second를 바꿔보세요

kkw564 6년 전 0

바보같은 짓을 했네요 지적해주셔서 감사합니다 !

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

문제

문제

출처

ICPC

priority queue 설정 질문입니다.

kkw564 6년 전 1

kkw564 6년 전 0

ntopia 6년 전 0

kkw564 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말