[백준 5719] 거의 최단 경로

요구사항

최단 경로를 제외한 나머지 중 최단 경로를 구하여라

 

풀이

최단 경로를 지우고 나서 최단 경로를 구하면 된다

단순히 다익스트라 문제처럼 보이지만 최단 경로를 지우는 구현, 아이디어가 힘든거 같다

 

1. 최단 경로 구한다

2. 최단 경로로 이어진 경로 삭제

 - 도착점부터 시작점까지의 최단 경로를 저장하는 경로가 있어야 한다.

 - 다익스트라 알고리즘을 구현할때, 새로운 dist로 갱신이 되면 그 경로가 end로 가기위한 경로중 하나이다.

 - 제일 끝점에서 부터 start까지 역순으로 탐색하여 최단 경로의 길이를 -1로 초기화 시켜준다

3. 거의 최단 경로 구하기

 

#include <iostream>
#include <cstdio>
#include <limits.h>
#include <memory.h>
#include <vector>
#include <queue>

using namespace std;
int n,m;
int startnode, endnode;
vector<pair<int,int>> graph[550];
vector<pair<int,int>> Minnode[550];
int dist[550];
void Getdistance(){
	//거리 초기화
	for(int i=0 ; 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 nownode= q.top().second;
		int nowdist = q.top().first;
		q.pop();

		for(int i=0 ; i <graph[nownode].size() ; i++){
			int nextnode = graph[nownode][i].first;
			int nextdist = graph[nownode][i].second;
			if(nextdist ==-1) continue;
			if(dist[nextnode] > nowdist + nextdist){
				dist[nextnode] = nowdist + nextdist;

				q.push({dist[nextnode],nextnode});
				Minnode[nextnode].clear();
				Minnode[nextnode].push_back({nownode,dist[nextnode]});
			}
			else if(dist[nextnode] == nowdist + nextdist){
				Minnode[nextnode].push_back({nownode,dist[nextnode]});
			}
		}
	}
}
int main()
{
	while(true){
		scanf("%d%d%d%d",&n,&m,&startnode,&endnode);
		if(n==0 && m==0) break;
		//입력 받기
		for(int i=0 ; i < n ; i++){ 
			graph[i].clear();
			Minnode[i].clear();
		}
		for(int i=0 ; i < m ; i++){
			int x, y,z;
			scanf("%d%d%d",&x,&y,&z);
			graph[x].push_back({y,z});
		}
		//최단 경로 구하기
		Getdistance();
		//최단 경로길 제거
		queue<int> que;
		que.push(endnode);
		while(!que.empty()){
			int now = que.front();
			que.pop();

			for(int i=0 ; i <Minnode[now].size();i++){
				int next = Minnode[now][i].first;
				for(int j=0; j< graph[next].size();j++){
					if(graph[next][j].first == now){
						graph[next][j].second=-1;
					}
				}
				que.push(next);
			}
		}
		//거의 최단 경로 구하기
		Getdistance();
		if(dist[endnode]==987654321) cout<<-1<<endl;
		else cout<< dist[endnode]<<endl;

		
	}
}