글 읽기 - 궁금해요!! 다익스트라의 조건이 위배되도 정답 처리되는것 같습니다.(가중치)

shfshfdl 6년 전 1

우선 코드 상에서

priority_queue <pair<int, int> > pq;
pq.push({ start, 0 });

로 선언을 하였습니다. 그렇다면 pair는 정렬을 할때 first를 먼저 정렬하고 second를 정렬하는것으로 아는데

그렇다면 이코드는 가중치를 우선으로 소팅하는게 아니라 index를 먼저 소팅하게 되어

가중치가 크더라도 먼저 선택이 되는 경우가 발생할 것 같은데

성공으로 처리가 되네요

우선 두 쌍의 순서를 바꿔도 동일하게 정답 처리가 됩니다.

제가 모르고 있는 부분이 있는지 궁금합니다!!1

감사합니다.

#include "stdio.h"
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321

int v, e;
int start;
vector <pair<int, int> > a[20001];

vector <int> dijkstra(int start) {
	vector <int> dist(v + 1, INF);
	dist[start] = 0;
	priority_queue <pair<int, int> > pq;
	pq.push({ start, 0 });
	while (!pq.empty()) {
		int here = pq.top().first;
		int weight = -pq.top().second;
		pq.pop();

		if (dist[here] < weight) continue;
		for (int i = 0; i < a[here].size(); i++){
			int there = a[here][i].first;
			int thereWeight = weight + a[here][i].second;

			if (dist[there] > thereWeight) {
				dist[there] = thereWeight;
				pq.push({ there, -thereWeight });
			}
		}
	}

	return dist;
}

int main() {
	scanf("%d %d", &v, &e);
	scanf("%d", &start);

	for (int i = 0; i < e; i++) {
		int from, to, w;
		scanf("%d %d %d", &from, &to, &w);
		a[from].push_back({ to, w });
	}
	vector <int> ans = dijkstra(start);
	for (int i = 1; i <= v; i++) {
		if (ans[i] == INF ) {
			printf("INF\n");
			continue;
		}
		printf("%d\n", ans[i]);
	}
	return 0;
}

kdk8361 6년 전 1

21번과 26번 줄에 비교구문을 넣어서 그런 듯 합니다. 다익스트라라기 보다는 bfs에 가까운 형태 같습니다.

제가 다익스트라 구현한 방식대로라면 dist비교를 하는게 아니라 -1로 초기화 한 후 -1이 아닌 경우, 즉 이미 들렀던 노드라면 continue 시켜버리기 때문에 pq pair 순서가 바뀌면 이상한 값이 들어가겠죠.

shfshfdl 6년 전 0

답변감사합니다.

답변 주신게 답인것 같습니다. ㅎㅎ
아직 이해가 될듯 말듯한 부분은 있으나 이부분은 최단경로 bfs로 한번
공부해보겠습니다. 약간 비슷한 느낌의 코드라 bfs에 가깝다는것도 몰랐네요

많은 도움 됬습니다. 감사합니다.

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

문제

문제

출처

ICPC

궁금해요!! 다익스트라의 조건이 위배되도 정답 처리되는것 같습니다.(가중치)

shfshfdl 6년 전 1

kdk8361 6년 전 1

shfshfdl 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말