글 읽기 - 다익스트라 질문

p_ce1052 3년 전 0

일반적인 다익스트라 알고리즘으로 구현하고 거리가 갱신될 때마다 pre[갱신된 곳] = 갱신한 곳 으로 pre배열을 만들어서 최단경로를 끝에서부터 역추적했습니다. 반례가 있을까요..?

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<limits>
using namespace std;
typedef pair<int,long long> pi;
vector<pi>graph[1001];
long long dist[1001];
int pre[1001];
const long long INF = numeric_limits<long long>::max();

void dijkstra(int start){
	bool visited[1001]={0};
	for(int i=0; i<=1000; i++) dist[i] = INF;
	dist[start] = 0;
	priority_queue<pi,vector<pi>,greater<pi> >pq;
	pq.push(pi(start,dist[start]));
	while(!pq.empty()){
		int curr;
		do{
			curr = pq.top().first;
			pq.pop();
		}while(!pq.empty() && visited[curr]);
		if(visited[curr]) break;
		visited[curr]=true;
		for(int i=0; i<graph[curr].size(); i++){
			int next = graph[curr][i].first;
			long long d = graph[curr][i].second;
			long long ret = dist[next];
			dist[next] = min(dist[next],dist[curr]+d);
			if(ret!=dist[next]) pre[next]=curr; //갱신되었다면 이전마을 수정  
			pq.push(pi(next,dist[next]));
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	long long input_table[n+1][n+1];
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++) input_table[i][j] = INF;
	}
	while(m--){
		int a,b;
		long long cost;
		cin>>a>>b>>cost;
		input_table[a][b] = min(input_table[a][b],cost);
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(input_table[i][j]!=INF) graph[i].push_back(pi(j,input_table[i][j]));
		}
	}
	int start,fin;
	cin>>start>>fin;
	dijkstra(start); //시작점에서 다익스트라 
	cout<<dist[fin]<<'\n'; //거리출력
	pre[start]=start; //시작점의 pre는 자기자신 
	int curr = fin;
	vector<int>res;
	while(pre[curr]!=curr){ //시작점이 아닐때까지 배열에 넣는다
		res.push_back(curr);
		curr = pre[curr];
	}
	res.push_back(start); //시작점을 넣는다 
	cout<<res.size()<<'\n'; //도시 개수
	for(int i=res.size()-1; i>=0; i--) cout<<res[i]<<" ";
}

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

문제

문제

출처

ICPC

다익스트라 질문

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말