백준 5719번 거의 최단 경로

< 백준 5719번 거의 최단 경로 - 마포 코딩박 >

사용한 알고리즘: 다익스트라


 단방향 간선들이 주어지고, 출발점에서 도착지점까지 가는 거의 최단 경로값을 출력하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (생각)
 먼저 다익스트라를 통해 최단경로에 쓰이는 간선을 찾아 체크해줍니다.
 이후 다익스트라를 한번 더 돌리는데, 앞서 체크된 사용한 간선은 사용하지 않습니다. 이는 거의 최단 경로가 될 것입니다.

(2) (코드 47~84)
 입력되는 간선정보를 토대로 다익스트라를 돌려 최단경로와 이때 쓰이는 간선을 저장합니다.

(2) (코드 85~87)
 과정(2)에서 저장한 간선들을 bool 배열로 체크해줍니다.

(3) (코드 88~112)
 최단경로에 쓰인 간선들을 제외한 간선들로 다익스트라를 한번 더 돌려서 거의 최단 경로값을 찾습니다.

	#include <iostream>
	#include <queue>
	#include <utility>
	#include <set>
	#include <tuple>
	#include <cstring>
	using namespace std;
	typedef pair<int, int> pii;
	typedef tuple<int, int, int> tp;
	const int MAX = 500;
	const int INF = 987654321;
	int N, M, S, D;
	// adj[x] : x 에서 갈 수 있는 점 < 위치, 거리, edge의 index >
	vector<tp> adj[MAX+1];
	// 쓰인 edge 의 index
	bool visited[10001];
	struct info{
	int len;
	vector<int> Use;
	};
	// dist[i] : S 에서 i 까지 거리 / 사용한 edge index
	info dist[MAX+1];
	struct cmp{
	bool operator()(pii a, pii b){
	return a.second > b.second;
	}
	};
	priority_queue<pii, vector<pii>, cmp> pq;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	while(1){
	cin >> N >> M;
	if(N==0&&M==0) break;
	cin >> S >> D;
	// 초기화
	memset(visited,false,sizeof(visited));
	for(int i=0; i<N; ++i){
	dist[i].len = INF;
	dist[i].Use.clear();
	adj[i].clear();
	}
	for(int i=0; i<M; ++i){
	int u, v, p;
	cin >> u >> v >> p;
	adj[u].push_back(tp(v,p,i));
	}
	dist[S].len = 0;
	pq.push(pii(S,0));
	while(!pq.empty()){
	int now = pq.top().first;
	int Distance = pq.top().second;
	pq.pop();
	// 중복방지
	if(dist[now].len < Distance) continue;
	for(auto next: adj[now]){
	int where = get<0>(next);
	int W = get<1>(next);
	int idx = get<2>(next);
	// now 를 통해 where 가는 경로값 = 기존 where 가는 최단 경로 값
	if(Distance + W == dist[where].len){
	// where 오는 경로에 now 통한 경로 추가
	dist[where].Use.push_back(idx);
	for(auto ch: dist[now].Use)
	dist[where].Use.push_back(ch);
	pq.push(pii(where,Distance+W));
	}
	// now를 통해 where 가는 경로값이 기존 where 가는 최단 경로값보다 작은경우
	else if(Distance + W < dist[where].len){
	dist[where].len = Distance + W;
	dist[where].Use.clear();
	dist[where].Use.push_back(idx);
	for(auto ch: dist[now].Use)
	dist[where].Use.push_back(ch);
	pq.push(pii(where,Distance+W));
	}
	}
	}
	// 최단경로에 쓰인 간선들을 true로 표시
	for(auto ch: dist[D].Use)
	visited[ch] = true;
	// 두번째 길 찾기~
	for(int i=0; i<N; ++i) dist[i].len = INF;
	dist[S].len = 0;
	pq.push(pii(S,0));
	while(!pq.empty()){
	int now = pq.top().first;
	int Distance = pq.top().second;
	pq.pop();
	if(dist[now].len < Distance) continue;
	for(auto next: adj[now]){
	int where = get<0>(next);
	int W = get<1>(next);
	int idx = get<2>(next);
	// 최단경로에 사용된 간선은 못쓴다.
	if(visited[idx]) continue;
	else if(Distance + W < dist[where].len){
	dist[where].len = Distance + W;
	pq.push(pii(where,Distance+W));
	}
	}
	}
	if(dist[D].len==INF) cout << -1 << '\n';
	else cout << dist[D].len << '\n';
	}
	return 0;
	}

view raw BOJ 5719.cpp hosted with ❤ by GitHub