글 읽기 - 다익스트라 시간초과 질문입니다.....

shingj92 3년 전 0

문제 풀이 부분인데요..

priority queue 사용했는데 시간초과 되더라구요..

priority queue가 높은 것 부터 찾아서 그렇다고 하는데 어떻게 고치면 될까요..?

v가 간선 vector 입니다.

#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>

#define INF (300000 * 10 + 1)

struct info {
	int to;
	int we;
	bool operator<(const info& o) const {
		return we > o.we;
	}
};
int V, E, K;

int dist[20001] = { 0, };
vector<info> v[20001];

...

void sol(int s)
{
	priority_queue<info> pq;
	pq.push({ s, 0 });
	dist[s] = 0;

	while (!pq.empty())
	{
		info cur = pq.top();
		pq.pop();

		if (cur.we > dist[cur.to])
			continue;
		for (info& nxt : v[cur.to]) {
			if (dist[cur.to] + nxt.we < dist[nxt.to]) {
				dist[nxt.to] = dist[cur.to] + nxt.we;
				pq.push({ nxt.to, dist[nxt.to] });
			}
		}
	}
}

shg9411 3년 전 0

pair의 경우 priority queue에서 first가 우선순위로 설정됩니다.

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

문제

문제

출처

ICPC

다익스트라 시간초과 질문입니다.....

shingj92 3년 전 0

shg9411 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말