글 읽기 - 다익스트라 기초문제 C++ 시간초과

pianosiwon 2년 전 0

왜 시간초과가 나는지 잘모르겠어요ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int,int>>v[20002];
int V, E, K;
#define INF 9999999
int d[20002];
priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(0);
	cin >> V >> E >> K;
	for (int i = 0; i < E; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
	}
	for (int i = 1; i <= V; i++) d[i] = INF;
	d[K] = 0;//시작노드부터 자신노드 까지 거리는 0이다
	q.push({ K,0 });
	while (!q.empty())
	{
		int node = q.top().first;
		int dist = q.top().second;
		q.pop();
		if (d[node] < dist) continue;
		for (int i = 0; i < v[node].size(); i++)
		{
			int pos = v[node][i].first;
			int new_dist = dist + v[node][i].second;
			if (d[pos] > new_dist)
			{
				d[pos] = new_dist;
				q.push({ pos,new_dist });
			}
		}

	}
	for (int i = 1; i <= V; i++)
	{
		if (d[i] == INF) cout << "INF\n";
		else cout << d[i] << "\n";
	}
    return 0;
}

eoehd1ek 2년 전 1

우선순위 큐에 { 노드번호, 가중치 } 순서로 넣으면

정렬이 노드 번호가 작은 순서, 같으면 가중치가 작은 순서로 우선순위 큐가 작동하기 때문에 생각하신 대로 동작하지 않는 것 같습니다.

비교 함수를 직접 작성해 넣으시거나 { 가중치, 노드번호 } 순으로 넣으시면 될 것 같습니다.

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

문제

문제

출처

ICPC

다익스트라 기초문제 C++ 시간초과

pianosiwon 2년 전 0

eoehd1ek 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말