글 읽기 - 우선순위큐를 이용해서 구현했습니다

luckyquit 4년 전 0

VLogE 가 시간 초과라니,,

제가 어떤부분을 잘못 구현한 것일까요?

예제 및 게시판의 반례들은 정상수행됩니다

#include<queue>
#include<iostream>
#include<vector>
#include<list>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef pair<int, int> pi;

priority_queue<pi, vector<pi>, greater<pi>> pq;
list<pi> *adj;

int V, E, start;

void Dijkstra_using_pq(void)
{
	vector<int> dist(V + 1, INF);

	pq.emplace(make_pair(start, 0));
	dist[start] = 0;

	while (!pq.empty()) {
		int u = pq.top().first;
		pq.pop();

		for(auto i : adj[u]) {
			int v = i.first;
			int weight = i.second;

			if (dist[v] > dist[u] + weight) {
				dist[v] = dist[u] + weight;
				pq.emplace(make_pair(v, dist[v]));
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		if (dist[i] == INF) cout << "INF";
		else cout << dist[i];

		cout << '\n';
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> V >> E >> start;

	adj = new list<pi>[V + 1];

	for (int i = 0; i < E; i++) {
		int u, v, w; cin >> u >> v >> w;
		adj[u].emplace_back(make_pair(v, w));  // u->v weight is w.
	}
	Dijkstra_using_pq();
}

clrmt 4년 전 1

간선의 무게가 아니라 간선의 인덱스가 낮은 순서로 뽑아내고 있습니다.

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

문제

문제

출처

ICPC

우선순위큐를 이용해서 구현했습니다

luckyquit 4년 전 0

clrmt 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말