백준 5719 거의 최단 경로

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

5719번: 거의 최단 경로

다익스트라 한 번 돌리고

최적경로 지우고

다익스트라 한 번 돌리면 풀 수 있는 문제다.

 

아이디어가 직관적으로 떠오르는데, 구현이 까다로운 문제

 

edge는 점과 Weight를 동시에 저장한다.

trace에 최적 경로를 저장한다. 

dist는 S로부터 모든 점까지의 최단 거리를 계산한다.

 

/* 거의 최단 경로 */

#include <iostream>
#include <queue>
#include <algorithm>

#define pp pair<int,int>
#define INTMAX 2100000000

using namespace std;

void init();
void input();
void solve();

int N, M, S, D; 
vector<pp> edge[501];
vector<int> trace[501];
int dist[501];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    
	while (true) {
		init();
		input();
		solve();
	}
	return 0;
}

void init() {
	for (int i = 0; i <= 500; i++) {
		edge[i].clear();
		trace[i].clear();
	}
}

void input() {
	cin >> N >> M;
    
    // 0이 들어오면 끝.
	if (N == 0 && M == 0) {
		exit(0);
	}

	cin >> S >> D;
	for (int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c;
		
		edge[a].push_back({ b,c });
	}
}

void dijkstra() {

	/* dist 배열 초기화 */
    for (int i = 0; i <= 500; i++) {
		dist[i] = INTMAX;
	}
    
    /* 시작점까지의 거리는 당연히 0이다 */
	dist[S] = 0;
	priority_queue<pp> pq;

	pq.push({ 0, S });

	while (!pq.empty()) {
    /* priority queue에서 최솟값이 제일 위로 오도록 하기 위해 - 를 붙인다 */
		int cost = -pq.top().first;
		int node = pq.top().second;
		
		pq.pop();

		if (cost > dist[node])
			continue;

		for (int i = 0; i < edge[node].size(); i++) {
			int nxtNode = edge[node][i].first;
			int nxtCost = edge[node][i].second + cost;

			if (edge[node][i].second == -1)
				continue;

			if (nxtCost < dist[nxtNode]) {
				dist[nxtNode] = nxtCost;
				pq.push({ -nxtCost, nxtNode });

				trace[nxtNode].clear();
				trace[nxtNode].push_back(node);
			}

			/* 같은 값이면 둘 다 최적 값이므로 둘 다 넣는다 */
			else if (nxtCost == dist[nxtNode]) {
				trace[nxtNode].push_back(node);
			}
		}
	}

}

void cutting(int after) {
	queue<int> q;
    
	bool is_visit[501] = { false, };
	is_visit[after] = true;
    
	q.push(after);
    
	while (!q.empty()) {
		int node = q.front();
		q.pop();		

		for (int i = 0; i < trace[node].size(); i++) {
			int beforeNode = trace[node][i];
			for (int j = 0; j < edge[beforeNode].size(); j++){
			
				if (edge[beforeNode][j].first == node) {
					edge[beforeNode][j].second = -1;
					break;
				}
			}

			q.push(beforeNode);
		}
	}
}

void solve() {
	dijkstra();
	cutting(D);
	dijkstra();
	if (dist[D] == INTMAX)
	{
		dist[D] = -1;
	}
	cout << dist[D] << '\n';

}