BOJ 5719 - 거의 최단 경로

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	11956	1484	936	21.389%

문제

---

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

입력

---

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 10⁴)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 10³) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

---

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

접근

---

다익스트라 기반의 응용 문제였다.
처음에 다익스트라로 D 까지의 거리를 구하되, 이전 노드들(복수)을 저장해놓고,
DFS로 순회하면서 해당 Edge들을 삭제해준 뒤 다시 다익스트라를 돌리면 될 것이라 생각했다.

N이 500이라 노드를 삭제하기 용이한 인접 행렬으로 풀이를 시작했었다.
다만, 테스트케이스가 몇 개인지를 몰랐던 것이 독이 되어 TLE가 떴다.
그래서 Map 기반의 인접 리스트로 풀이를 했는데도 TLE가 떴다.
알고보니 DFS로 노드를 삭제하는 과정에서 중복 처리를 해주지 않았던 것이었다.
메모이제이션은 항상 중요하다.

풀이

---

첫 다익스트라를 돌릴 때는 before 벡터를 만들어서 이전 노드들을 저장했다.
그리고 DFS로 삭제하는 과정에서 iterator를 erase해줘서 중복 접근을 막았다.
이후에는 한번 더 S에서 다익스트라를 돌려주면 된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

const int INF = 987654321;
int N, M, S, D, arr[500], u, v, w;
vector<int> before[500];
map<int, int> dist[500];

void DFS(int node)
{
	auto iter = before[node].begin();
	while(!before[node].empty())
	{
		dist[*iter][node] = -1;
		DFS(*iter);
		iter = before[node].erase(iter);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	while (true)
	{
		CIN2(N, M);
		if (!N) break;
		CIN2(S, D);
		FUP(i, 0, N - 1)
		{
			dist[i].clear();
			arr[i] = INF;
			before[i].clear();
		}
		while (M--)
		{
			CIN3(u, v, w);
			dist[u][v] = w;
		}
		priority_queue<pair<int, int>> pq; // {거리, 노드}
		arr[S] = 0;
		pq.push({ 0, S });
		while (!pq.empty())
		{
			int node = pq.top().second;
			int d = -pq.top().first;
			pq.pop();
			if (node == D) break;
			for(auto p : dist[node])
			{
				int nd = p.second + d;
				if (nd > arr[p.first]) continue;
				else if (nd == arr[p.first]) before[p.first].push_back(node);
				else
				{
					before[p.first].clear();
					before[p.first].push_back(node);
					arr[p.first] = nd;
					pq.push({ -nd, p.first });
				}
			}
		}
		while (!pq.empty()) { pq.pop(); }
		DFS(D);

		FUP(i, 0, N - 1) arr[i] = INF;
		arr[S] = 0;
		pq.push({ 0, S });
		while (!pq.empty())
		{
			int node = pq.top().second;
			int d = -pq.top().first;
			pq.pop();
			if (node == D) break;
			for (auto p : dist[node])
			{
				if (p.second == -1 || p.second + d >= arr[p.first]) continue;
				arr[p.first] = d + p.second;
				pq.push({ -arr[p.first], p.first });
			}
		}
		arr[D] == INF ? COUT(-1) : COUT(arr[D]);
		ENDL;
	}

	return 0;
}