글 읽기 - 다익스트라로 해결이 불가능한가요??

easter3163 7년 전 0

혹시 같이 고민해주실수 있나요

#include <stdio.h>
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
int N, M;
vector<vector<pair<int, long long int> > > graph;
vector<long long> dijkstra(int src){
	vector<long long int> dist(N + 1, LLONG_MAX);
	dist[src] = 0;
	priority_queue<pair<int, long long int> > q;
	q.push(make_pair(src, 0));
	while (!q.empty()){
		int now = q.top().first;
		long long int now_dist = -q.top().second;
		q.pop();
		if (dist[now] < now_dist){
			continue;
		}
		int len = graph[now].size();
		for (int i = 0; i < len; i++){
			int next = graph[now][i].first;
			long long int next_dist = now_dist + graph[now][i].second;
			if (next_dist < dist[next]){
				dist[next] = next_dist;
				q.push(make_pair(next, -next_dist));
			}
		}
	}
	return dist;
}
int main(void){
	cin >> N; cin >> M;
	graph.resize(N + 1);
	while (M--){
		int u, v;
		long long int x;
		cin >> u; cin >> v; cin >> x;
		graph[u].push_back(make_pair(v, x));
		graph[v].push_back(make_pair(u, x));
	}
	int start, end;
	cin >> start; cin >> end;
	vector<long long int> dist = dijkstra(start);
	printf("%lld", dist[end]);
}

portableangel 7년 전 2

1. 우선, 다익스트라 구현이 잘못되었습니다.

정점 번호와 거리를 저장하는 pair를 만드실 때, (정점,-거리) 순으로 저장하셨는데 이 경우 거리와는 관계없이 정점 번호가 가장 큰 정점부터 방문을 시작하게 됩니다.

(-거리,정점) 순으로 저장하도록 고쳐주세요. 예를 들면 13번 줄, 27번 줄 등등..

2. 문제의 의미를 잘못 파악하셨습니다. 최단 경로를 찾는 문제가 아닙니다.. 문제를 다시 읽어보세요.

각 간선의 가중치는 거리가 아닌, 해당 간선을 지날 수 있는 무게의 상한입니다.

easter3163 7년 전 0

아 감사합니다 납득할 것 같네요 다시 해보겠습니다

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

문제

문제

출처

ICPC

다익스트라로 해결이 불가능한가요??

easter3163 7년 전 0

portableangel 7년 전 2

easter3163 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말