[백준 1719] 택배

분류 : 다익스트라

 

요구사항

각 정점까지 최소로 가기 위해 첫번째로 거쳐야하는 정점은 무엇인가

 

풀이

일단 기본적인 다익스트라에다가 경로 추적을 더해준다

경로는 길이가 업데이트 될때 경로도 업데이트해준다

업데이트 될때마다 경로는 next 노드로 오려면 now로 부터 와야한다는 의미가 된다

 

출력시 startnode가 될때까지 경로를 돌려주면 된다

 

#include <stdio.h>
#include <map>
#include <algorithm>
//#include "Windows.h"
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <math.h>

using namespace std;
struct go{
	int x;
	int y;
};
int n,m;
int dist[220];
int getdist[220];
vector<go> graph[220];
int main(){
	scanf("%d%d",&n,&m);
	for(int i =0 ; i < m ; i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		graph[x].push_back({y,z});
		graph[y].push_back({x,z});
	}

	for(int startnode= 1; startnode <= n ; startnode++){
		for(int i=1; i<=n ; i++) dist[i]=987654321;
		dist[startnode]=0;
		priority_queue<pair<int,int> , vector<pair<int,int> > , greater<>> q;
		q.push({0,startnode});
		while(!q.empty()){
			int nowdist = q.top().first;
			int nownode = q.top().second;
			q.pop();
			for(int i=0; i <graph[nownode].size() ; i++){
				int nextnode = graph[nownode][i].x;
				int nextdist = graph[nownode][i].y;
				if(dist[nextnode] > nowdist + nextdist){
					dist[nextnode] = nowdist + nextdist;
					getdist[nextnode] = nownode;
					q.push({dist[nextnode],nextnode});
				}
			}
		}
		for(int i=1; i <=n ; i++){
		//	cout<<"A"<<i<<endl;
			if(i==startnode){
				printf("- ");
			}
			else if(getdist[i]==startnode){
				printf("%d ", i);
			}
			else{
				int cur=i;
				while(true){
					if(getdist[cur]==startnode){
						printf("%d ",cur);
						break;
					}
					else{
					cur=getdist[cur];
					}
				}
			}
		}
		printf("\n");
	}
}