[백준] 5719: 거의 최단 경로 (수정)

0. 문제 주소

 

https://www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

 

 

1. 풀이

 

최단 경로가 여러개일 수 있고, 그 여러 최단 경로끼리도 간선을 공유할 수 있다.

 

풀이는 다음과 같다.

 

 

0. 문제에서 주어지는 방향 간선으로 그래프를 만들고, 그 역방향 간선으로 별도의 그래프를 만들어 둔다.

 

1. 다익스트라 알고리즘을 적용한다.

 

2. 도착점에서부터 역방향 간선으로 만든 그래프를 순회하며, 현재의 노드를 curr, 다음 노드를 next, 가중치를 weight이라고 하면, dist[curr] - weight = dist[next]를 만족하는 경우 (next, curr) 간선은 최단 경로에 포함되는 간선이다. 

역방향으로 BFS 순회를 할 때 이미 최단 경로에 포함되었다고 확인했던 간선이면 continue 해주어야 한다. (Line 85) 재채점돼서 MLE 떴다가 다시 AC 띄우는데 고생함 ㅠ

 

3. 이를 avail 배열에 저장한다. ( avail[i][j] = (i, j) 간선이 최단 경로에 포함되는 경우 true)

 

4. 다시 한번 다익스트라를 적용하되 최단 경로에 포함된 경우 그 간선은 이용하지 않는다.

 

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>

#define pii pair<int, int>
#define MAX 503
#define INF 987654321

using namespace std;

int N, M, S, D;
int dist[MAX];
bool available[MAX][MAX]; // available[i][j] = i -> j로 가는 간선은 최단 경로에 포함됨. 
bool visited[MAX];
vector<pii> graph[MAX];
vector<pii> rev_graph[MAX];

int main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	#endif
	
	while(1){
		
		scanf("%d %d", &N, &M);
		if (N==0 && M==0) break;
		
		for (int i=0;i<N;i++){
			dist[i] = INF;
		}
		memset(visited, 0, sizeof(visited));
		memset(available, 0, sizeof(available));
		
		for (int i=0;i<N;i++){
			graph[i].clear();
			rev_graph[i].clear();
		}
		priority_queue<pii, vector<pii>, greater<pii>> PQ;
		
		
		scanf("%d %d", &S, &D);
		
		
		for (int i=0;i<M;i++){
			int u, v, w;
			scanf("%d %d %d", &u, &v, &w);
			graph[u].push_back(pii(v, w));
			rev_graph[v].push_back(pii(u, w));
		}
		
		dist[S] = 0;
		PQ.push(pii(0, S));
		
		while(!PQ.empty()){
			auto p = PQ.top();
			PQ.pop();
			int curr = p.second, curr_dist = p.first;
            if (dist[curr] < curr_dist) continue;
			// visited[curr] = true;
			for (auto pp: graph[curr]){
				int next = pp.first, weight = pp.second;
				if (dist[next] > curr_dist + weight){
					dist[next] = curr_dist + weight;
					PQ.push(pii(dist[next], next));
				}
			}
		}
		if (dist[D] == INF) {
			printf("-1\n");
			continue;
		}
		
		queue<pii> Q;
		Q.push(pii(D, dist[D]));
		while(!Q.empty()){
			auto pp = Q.front();
			int curr = pp.first, curr_remain = pp.second;
			Q.pop();
            if (curr == S) continue;            
			for (auto ppp: rev_graph[curr]){
				int next = ppp.first, weight = ppp.second;
                if (available[next][curr]) continue;
				if (curr_remain - weight == dist[next]){
					available[next][curr] = true;
					Q.push(pii(next, dist[next]));
				}
			}
		}
		
//		for (int i=0;i<N;i++){
//			for (int j=0;j<N;j++){
//				printf("%d ", available[i][j]);
//			}
//			printf("\n");
//		}
//		printf("\n");
		
		for (int i=0;i<N;i++){
			dist[i] = INF;
		}
		// memset(visited, 0, sizeof(visited));
		
		dist[S] = 0;
		PQ.push(pii(0, S));
		while(!PQ.empty()){
			auto p = PQ.top();
			PQ.pop();
			int curr = p.second, curr_dist = p.first;
            if (dist[curr] < curr_dist) continue;
			// visited[curr] = true;
			for (auto pp: graph[curr]){
				int next = pp.first, weight = pp.second;
				if (!available[curr][next] && dist[next] > curr_dist + weight){
					dist[next] = curr_dist + weight;
					PQ.push(pii(dist[next], next));
				}
			}
		}
		if (dist[D] == INF) printf("-1\n");
		else printf("%d\n", dist[D]);
		
	} 
	
	return 0;
}