[백준/BOJ] 백준 5719번 : 거의 최단 경로

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

5719번: 거의 최단 경로

다익스트라 알고리즘을 이용하여 문제를 해결했다. 시작점에서 도착점으로 가는 최단경로를 통해 해당 경로에 속하는 길들을 저장한 뒤, 체크해 두었고, 다시 시작점에서 도착점으로 가는 다익스트라 알고리즘을 사용하는데 이때 체크해둔 길로는 이동하지 못하도록 하는 방법을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> output;
int n, m;
int s, d;
vector<pair<int, int>> adj[500]; //(길이, 목적지)
vector<int> come_from[500]; //[there] = (here,...)
vector<vector<int>> short_dist_check(500, vector<int>(500, 0));
vector<int> checked(500, 0);

void Pre()
{
	for (int i = 0; i < 500; i++)
	{
		adj[i].clear();
		come_from[i].clear();
		checked[i] = 0;

		for (int j = 0; j < 500; j++)
		{
			short_dist_check[i][j] = 0;
		}
	}
}

//최단경로에 속하는 길 체크
void Check_short_dist(int there)
{
	//there에 연결된 길은 체크했다고 표시
	checked[there] = 1;

	for (int i = 0; i < come_from[there].size(); i++)
	{
		int here = come_from[there][i];
		short_dist_check[here][there] = 1;

		if (checked[here] == 0)
			Check_short_dist(here);
	}
}

int Short_dist(int start, int dest)
{
	vector<int> result(500, 987654321);
	priority_queue<pair<int, int>> pq;

	result[start] = 0;
	pq.push(make_pair(-0, start));

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

		if (here_cost > result[here])
			continue;

		if (here == dest)
			return here_cost;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (there_cost < result[there])
			{
				come_from[there].clear();
				come_from[there].push_back(here);

				result[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}

			else if (there_cost == result[there])
			{
				come_from[there].push_back(here);
			}
		}
	}

	return -1;
}

int Solve(int start, int dest)
{
	vector<int> result(500, 987654321);
	priority_queue<pair<int, int>> pq;

	result[start] = 0;
	pq.push(make_pair(-0, start));

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

		if (here_cost > result[here])
			continue;

		if (here == dest)
			return here_cost;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			//here에서 there로 가는 길이 최단 경로에 속하는 길인지 확인
			if (short_dist_check[here][there] == 1)
				continue;

			if (there_cost < result[there])
			{
				result[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}
		}
	}

	return -1;
}

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


	while (1)
	{
		Pre();

		cin >> n >> m;

		if (n == 0 && m == 0)
			break;

		cin >> s >> d;

		for (int i = 0; i < m; i++)
		{
			int u, v, p;

			cin >> u >> v >> p;
			adj[u].push_back(make_pair(p, v));
		}

		int short_len = Short_dist(s, d);

		if (short_len == -1)
		{
			output.push_back(-1);
			continue;
		}

		Check_short_dist(d); //최단경로에 속하는길 체크

		int result = Solve(s, d);
		output.push_back(result);
	}

	for (int i = 0; i < output.size(); i++)
		cout << output[i] << "\n";

	return 0;
}