BOJ 5719 거의 최단 경로

사용한 알고리즘

다익스트라 알고리즘, DFS

알고리즘 설명

주어진 간선을 이용하여 그래프를 구성한다.
최단 경로를 구하기 위해 시작점으로 부터 다익스트라 알고리즘을 적용한다.
시작점으로 부터의 최단거리와 DFS를 이용하여 S->D까지 최단경로를 찾는다.
S->D 까지 가는 최단경로를 제외한 뒤 다시 한 번 다익스트라 알고리즘을 적용한다.
도착점까지 거의 최단 거리를 출력한다.

풀이

// baekjoon 5719 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> Pii;

const int MAX_N=501;
const int MAX_M=10001;
const int MAX_INF=1e9;

int T, N, M, S, D, U, V, P;
int adj[MAX_N][MAX_N];
int dist[MAX_N];
bool visited[MAX_N];

// 다익스트라 알고리즘
void Dijkstra() {
	fill(dist, dist+N, MAX_INF);
	memset(visited, 0, sizeof(visited));
	priority_queue<Pii, vector<Pii>, greater<Pii> > PQ;
	dist[S]=0;
	PQ.push(Pii(0, S));
	while (!PQ.empty()) {
		int cur;
		do {
			cur = PQ.top().second;
			PQ.pop();
		} while (!PQ.empty() && visited[cur]);
		if (visited[cur]) break;
		visited[cur]=true;
		for (int i=0; i<N; i++) {
			if (!adj[cur][i]) continue;
			if (dist[i] > dist[cur] + adj[cur][i]) {
				dist[i] = dist[cur] + adj[cur][i];
				PQ.push(Pii(dist[i], i));
			}
		}
	}
}

bool DFS(int here) {
// 도착점인 경우 DFS 종료
	if (here == D) return true;
// 현재로 부터 도착점으로 가는 경로가 이미 있는 경우 return true
	if (visited[here]) return true;

	for (int i=0; i<N; i++) {
		if (!adj[here][i]) continue;
// 최단 경로인지 확인
		if (dist[i] == dist[here] + adj[here][i]) {
// 도착점까지 가는 경로인지 확인
			if (DFS(i)) {
// 도착점까지 가는 최단 경로라면 지우고 현재 노드는 도착점까지 가능함을 visited에 체크
				adj[here][i]=0;
				visited[here]=true;
			}
		}
	}
	return visited[here];
}

// 최단경로 Edge를 제거함
void removeEdge() {
	memset(visited, 0, sizeof(visited));
	DFS(S);
}

int main() {
	while (1) {
		scanf("%d%d", &N, &M);
		if (!N && !M) break;
		memset(adj, 0, sizeof(adj));
		scanf("%d%d", &S, &D);
// 그래프 구성하기
		while (M--) {
			scanf("%d%d%d", &U, &V, &P);
			adj[U][V]=P;
		}
// 시작점으로 부터 최단 거리 구하기
		Dijkstra();
// 시작점부터 도착점까지 최단 경로 지우기
		removeEdge();
// 위 최단 경로를 제외한 거의 최단 거리 구하기
		Dijkstra();

// 결과 출력
		if (dist[D] == MAX_INF) puts("-1");
		else printf("%d\n", dist[D]);
	}
	return 0;
}