글 읽기 - 다익스트라 통과 실패.. (C++)

tngus1140 2년 전 0

안녕하세요! 오랫만에 백준으로 돌아와 문제를 풀고있는 한 유저입니다.

다름이 아니라 예전에 다익스트라 알고리즘을 공부한 적이 있어 시험삼아 풀어보려고 해당 문제를 도전했습니다.

일단 시간 초과를 방지하기 위해 인접 행렬이 아닌 인접 리스트를 사용하였으며 비트마스크를 사용하여 방문 유무를 확인했습니다.

INF도 넉넉하게 999999999로 두었고, struct를 만들었기 때문에 가중치(거리)가 낮은 그래프부터 우선순위큐의 top에 위치하도록 compare 함수를 만들었습니다.

게시판에 올라와있는 대부분의 예제를 적용시켰으나 아쉽게 반례를 찾지 못했습니다.

어떤 부분을 잘못 작성하여 통과하지 못하는 걸까요..

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

using namespace std;

#define INF 999999999

struct Node {
	int weight, index;
};

struct compare {
	bool operator()(const Node& left, const Node& right) const{
		if (left.weight != right.weight)
			return left.weight > right.weight;
		else
			return left.index > right.index;
	}
};

int main(void) {
	int V, E, S, a, b, w;
	cin >> V >> E >> S;

	vector<vector<Node>> list(V + 1);
	vector<int> dist(V + 1, INF);

	dist[S] = 0;
	
	for (int i = 0; i < E; i++) {
		cin >> a >> b >> w;

		list[a].emplace_back(Node{ w, b });
	}

	//dijkstra
	priority_queue<Node, vector<Node>, compare> pq;
	pq.push({ 0, S });
	int bit = 0, weight, idx, linkIdx, linkWeight;

	while (!pq.empty()) {
		weight = pq.top().weight;
		idx = pq.top().index;

		pq.pop();

		for (const Node& node : list[idx]) {
			linkIdx = node.index;
			linkWeight = node.weight;

			if (bit & (1 << linkIdx))continue;

			if (dist[linkIdx] > weight + linkWeight) {
				dist[linkIdx] = weight + linkWeight;

				pq.push({ dist[linkIdx], linkIdx });
			}
		}

		bit |= (1 << idx);
	}

	//print
	for (int i = 1; i <= V; i++) {
		if (dist[i] != INF) 
			cout << dist[i] << '\n';
		else
			cout << "INF" << '\n';
	}

	return 0;
}

WeissBlume 2년 전 1

https://www.acmicpc.net/board/... 와 동일한 문제를 갖고있으며, 노드의 개수가 1000개인 반면 bit는 32비트라 잘못된 동작을 합니다.

tngus1140 2년 전 1

아..! 맞네요

bit가 32비트니까 32개의 노드밖에 저장을 못하겠군요..

비트로 방문 처리하는걸 최근에 배워서 써먹으려고 했는데.. 역시 알고 써먹어야 되네요 ㅎㅎ.. 잘 기억하겠습니다!

빠른 댓글 감사합니다 WeissBlume님!

int bit 자체를 vector<bool> visited(V)로 바꿔서 해결했습니다.

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

문제

문제

출처

ICPC

다익스트라 통과 실패.. (C++)

tngus1140 2년 전 0

WeissBlume 2년 전 1

tngus1140 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말