BOJ 백준 5719 거의 최단경로 <다익스트라>

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

< 거의 최단 경로 >

 이 문제는 크게 한번 뻘짓(?)을 했다.

처음 문제를 잘못 이해해서, 최단경로에 사용되는 경로들을 지우지 않고 두 번째 최단경로를 구해주면 되는 줄 알고,

도착점 e와 연결된 노드들의 최단경로들 중에 2번째로 큰 수를 골라 출력해주는 형태로 하려고 했는데, 당연히 이 풀이는 틀렸다.

그 이유는 최단 경로에 사용된 경로들은 모두 제거해주어야 되기 때문이다.

따라서 이 문제는 먼저 다익스트라 알고리즘으로 최단 경로를 구해주고, 모든 최단 경로에 이용된 경로들을 제거해준 뒤

다시 다익스트라 알고리즘을 실행해서 최단경로를 출력해주면 된다.

Dijkstra();

DeletePath();

Dijkstra();

다익스트라 알고리즘에서 최단 경로에 이용된 경로들을 제거해주는 함수 DeletePath()는 bfs를 통해 구현할 수 있다.

bfs에서 처음 queue에 푸쉬하는 노드는 도착점이기 때문에, 도착점으로부터 시작점가지 거슬러 올라가야 한다.

이 말은, vector에 푸쉬하는 형태로 다익스트라를 푼 사람은 푸쉬해줄 때 그 반대 방향의 경로를 저장해줄 vector 하나를 더 만들어야 한다.

아래의 코드에서는 다익스트라를 풀 정방향 v 벡터와 bfs를 통해 경로를 제거해 줄 때 사용할 v_r 벡터를 선언하여 이용했다.

#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>

#define SIZE	501
#define INF	1000000000

using namespace std;
int n, m, s, e;

int iDist[SIZE];

void Dijkstra(vector< pair<int, int> > v[], bool (*visit)[SIZE])
{
	for (int i = 0; i < n; ++i) iDist[i] = INF;

	iDist[s] = 0;
	priority_queue< pair<int, int> > pq;
	pq.push({ 0, s });

	while(!pq.empty())
	{
		int iCost = -pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		if (iDist[cur_node] < iCost) continue;

		for (pair<int, int> p : v[cur_node])
		{
			int next_node = p.first;
			int next_cost = p.second + iDist[cur_node];

			if (visit[cur_node][next_node]) continue;

			if (iDist[next_node] > next_cost)
			{
				iDist[next_node] = next_cost;
				pq.push({ -next_cost, next_node });
			}
		}
	}
}

void DeletePath(vector< pair<int, int> > v_r[], bool (*visit)[SIZE])
{
	queue<int> q;
	q.push(e);

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		if (cur == s) continue;

		for (pair<int, int> p : v_r[cur])
		{
			int prev_node = p.first;

			if (iDist[prev_node] + p.second == iDist[cur])
			{
				visit[prev_node][cur] = true;
				q.push(prev_node);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	while (1)
	{
		cin >> n >> m;
		if (n == 0 && m == 0) break;

		cin >> s >> e;

		vector< pair<int, int> > v[SIZE];
		vector< pair<int, int> > v_r[SIZE];

		bool visit[SIZE][SIZE];
		memset(visit, 0, sizeof(visit));

		for (int i = 0; i < m; ++i)
		{
			int x, y, iDis;
			cin >> x >> y >> iDis;

			v[x].push_back({ y, iDis });
			v_r[y].push_back({ x, iDis });
		}

		Dijkstra(v, visit);
		DeletePath(v_r, visit);
		Dijkstra(v, visit);

		if (iDist[e] != INF)
			cout << iDist[e] << '\n';
		else
			cout << "-1" << '\n';
	}

	return 0;
}