글 읽기 - 시간초과 뜨는 것좀 봐주세요ㅠㅠㅠㅠ

danielkang1003 4년 전 0

안녕하세요. 다익스트라 접하고 풀고 있는데 시간초과가 뜨는데 어디서 뜨는건지 한번만 봐주시고 뭐가 문제인지 알려주시면 정말 너무나도 감사하겠습니다ㅠㅠㅠㅠ

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int INF = 987654321;
int v, e, k, u1, u2, w;
vector<pair<int, int>> adj[20001];

vector<int> dijkstra() {
	vector<int> dist(v, INF);
	dist[k] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ k, 0 });
	while (!pq.empty()) {
		int cur = pq.top().first;
		int cost = -pq.top().second;
		pq.pop();

		if (dist[cur] < cost) continue;
		
		int size = adj[cur].size();
		for (int i = 0; i < size; i++) {
			int next = adj[cur][i].first;
			int nextCost = cost + adj[cur][i].second;
			if (dist[next] > nextCost) {
				dist[next] = nextCost;
				pq.push({ next, -nextCost });
			}
		}
	}
	return dist;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> v >> e >> k;
	v++;
	for (int i = 1; i <= e; i++) {
		cin >> u1 >> u2 >> w;
		adj[u1].push_back({ u2, w });
	}

	vector<int> answer = dijkstra();

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

ha_ram 4년 전 1

priority queue에 문제가 있네요

가장 가중치가 작은것부터 꺼내야 하는데

priority queue에 넣을 때 {next, -nextCost} 이렇게 넣으시면

pair의 비교조건에 따라서 first먼저 비교하여 first가 높은게 priority queue에 가장 위쪽으로 가게 되어서

다익스트라 알고리즘이 제대로 작동하지 않게 됩니다.

ha_ram 4년 전 1

아마 예상해보자면

15번째 줄을 pq.push({ 0, k });

17번째 줄을 int cur = pq.top().second;

18번째 줄을 int cost = -pq.top().first;

29번째 줄을 pq.push({ -nextCost, next });

이렇게 바꾸면 통과될것 같네요

djm03178 4년 전 1

https://www.acmicpc.net/board/...

danielkang1003 4년 전 0

ha_ram님 감사합니다..ㅠㅠ아직 정확하게 다익스트라 사용법이 숙지가 안되었나봅니다. 다시 배워서 풀어보겠습니다!

djm03178 님 정말 감사합니다!제가 왜 틀렸는지 저기에 다 들어있군요..!!

두분 정말 모두 감사드립니다~!

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

문제

문제

출처

ICPC

시간초과 뜨는 것좀 봐주세요ㅠㅠㅠㅠ

danielkang1003 4년 전 0

ha_ram 4년 전 1

ha_ram 4년 전 1

djm03178 4년 전 1

danielkang1003 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말