글 읽기 - 다익스트라 입문 질문드립니다

ohyeons 4년 전 0

틀렸다고 나오는 걸로봐선 제가 틀리게 짠게맞는거같은데 어디서 틀렸는지를 잘 모르겠습니다 도와주세요

#include <iostream>
#include <algorithm>
#include <cstring> //memset
#include <cmath>
#include <vector>
#include <queue>
#include <string>

#define INF 987654321
typedef long long ll;
using namespace std;
//int g[20001][20001];
vector<pair<int,int>>g[20001];
int v, e, k;
int dist[20001];
bool vi[20001];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>pq;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> v >> e >> k;
	int a, b, c;
	for (int i = 1; i <= v; i++) {
		dist[i] = INF;
	}
	dist[k] = 0;
	for (int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		g[a].push_back({b,c});
	}
	pq.push({ k,0 });//시작정점,비용
	while (!pq.empty()) {
		int here = pq.top().first;
		int cost = pq.top().second;
		pq.pop();
		if (vi[here])continue;
		vi[here] = 1;
		dist[here] = cost;
		for (pair<int, int> next : g[here]) {
			if (vi[next.first])continue;
			next.second += cost;
			pq.push(next);
		}
	}
	for (int i = 1; i <= v; i++) {
		if (dist[i] == INF)cout << "INF\n";
		else cout << dist[i] << "\n";
	}
	return 0;
}

iooqooo 4년 전 0

pq에 pair( 간선 번호, 간선 가중치 )로 넣으시면

pii 기본 내림차순 정렬법에 따라서 간선번호가 작은것 부터 우선적으로 나오게 됩니다

그래서 pair의 second부분을 우선적으로 내림차순으로 정렬하라는 구조체를 만들어 pq의 우선순위를 정해주는데, 그게 귀찮으시면 그냥 pq에 넣을 땐 (간선 가중치, 간선 번호)로 해주시고 순서만 조절해주셔도 됩니다. 저도 그렇게 하구요

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

문제

문제

출처

ICPC

다익스트라 입문 질문드립니다

ohyeons 4년 전 0

iooqooo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말