[BOJ] 백준 5719번(C++): 거의 최단 경로/Dijkstra

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

5719번: 거의 최단 경로

추천받아서 풀게된 무시무시한 플레 다익스트라 문제

일반 최단경로를 제외했을 때의 '거의 최단경로'를 구하는 문제다

그래서 음 prev를 구해서 체크해준 다음 다익스트라를 다시 돌리면 되지 않을까?생각했는데 접근 방법은 맞았다

위의 그림처럼 다익스트라를 수행하면서 prev를 저장하고(최단경로가 두 개 이상 존재할 수 있기 때문에 배열로 저장)

해당 경로를 삭제 or 접근 불가능으로 만들고

다시 다익스트라 알고리즘을 수행하면 두 번째 최단경로를 얻을 수 있다

 

최단 거리만이 아닌 최단 경로를 구했어야 했기 때문에 바로 prev 배열을 사용할 거라는 생각이 들었따 

 

왼: 틀 / 오: 맞

하지만 끊임없는 메모리초과 맞왜틀을 겪엇고 결국 문제점을 찾아냈다

dist 값을 갱신할 수 있을 때 에만(기존 경로보다 거리가 짧을 때 에만) queue에 push해주었어야 했는데

코드 길이를 줄이려다 보니 이 부분을 간과해버렸었다

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define INF 500000001
#define pii pair<int,int>
using namespace std;

int n, m, s, d;
vector<vector<pii>> g;
vector<vector<int>> prv;
bool check[501][501];

bool input() {
	g.clear(); prv.clear();
	scanf("%d%d", &n, &m);
	if (!n && !m)return false;
	memset(check, false, sizeof check);

	scanf("%d%d", &s, &d);
	g = vector<vector<pii>>(n + 1);

	for (int i = 0, u, v, p; i < m; i++) {
		scanf("%d%d%d", &u, &v, &p);
		g[u].push_back(make_pair(p, v));
	}
	return true;
}

int dijkstra() {
	vector<int> dist(n + 1, INF);
	priority_queue<pii, vector<pii>, greater<>> pq;
	prv = vector<vector<int>>(n + 1);


	pq.push(make_pair(0, s));
	dist[s] = 0;

	while (!pq.empty()) {
		int cur = pq.top().second;
		int cost = pq.top().first; pq.pop();
		if (cost > dist[cur])continue;

		for (auto x : g[cur]) {
			if (check[cur][x.second])continue;

			int next = x.second;
			int ncost = x.first;

			if (dist[next] == dist[cur] + ncost) {
				prv[next].push_back(cur);
			}

			if (dist[next] > dist[cur] + ncost) {
				prv[next].clear();
				prv[next].push_back(cur);
				dist[next] = dist[cur] + ncost;
				pq.push(make_pair(dist[next], next));
			}
		}
	}

	return dist[d] == INF ? -1 : dist[d];
}

void erase(int cur) {
	for (auto x : prv[cur]) {
		for (int i = 0; i < g[x].size(); i++) {
			if (g[x][i].second == cur && !check[x][cur]) {
				check[x][cur] = true;
				erase(x);
				break;
			}
		}
	}
}

int main() {
	while (input()) {
		dijkstra();
		erase(d);
		printf("%d\n", dijkstra());
	}
	return 0;
}