[백준/BOJ] 백준 2325번 : 개코전쟁

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

2325번: 개코전쟁

1번부터 n번까지 최단경로를 구한 뒤 최단경로에 속하는 간선들을 저장하고 최단 경로에 속한 각각의 간선들이 없을 경우에 대한 최단경로를 구해 문제를 해결했다.

 

코드

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

int n, m;
vector<pair<int, int>> adj[1001];
vector<pair<int, int>> edge;
vector<int> path;
vector<int> come_from(1001, 0); //최단 경로로 이동할때 해당 지점으로 어디서 왔는지

void ShortSolve(int start)
{
	vector<int> result(1001, 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 == n)
			break;

		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])
			{
				result[there] = there_cost;
				come_from[there] = here;
				pq.push(make_pair(-there_cost, there));
			}
		}
	}
}

void MakePath(int here)
{
	path.push_back(here);

	int there = come_from[here];

	//here가 시작점이 아닐때
	if (there != 0)
		MakePath(there);
}

int Solve(int start)
{
	vector<vector<int>> result(1001, vector<int>(1000, 987654321)); //[정점][최단경로중 지나가지 않을 간선 번호]
	priority_queue<tuple<int, int, int>> pq; //(-비용, 위치, 최단경로중 지나가지 않을 간선 번호)

	for (int i = 0; i < edge.size(); i++)
	{
		result[start][i] = 987654321;
		pq.push(make_tuple(-0, start, i));
	}

	while (!pq.empty())
	{
		int here = get<1>(pq.top());
		int here_cost = -get<0>(pq.top());
		int break_edge = get<2>(pq.top());
		pq.pop();

		if (here_cost > result[here][break_edge])
			continue;

		if (here == n)
			continue;

		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 (edge[break_edge].first == min(here, there) && edge[break_edge].second == max(here, there))
				continue;

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

	int ret = -1;
	for (int i = 0; i < edge.size(); i++)
	{
		ret = max(ret, result[n][i]);
	}

	return ret;
}

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

	cin >> n >> m;

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

		adj[x].push_back(make_pair(z, y));
		adj[y].push_back(make_pair(z, x));
	}

	ShortSolve(1);

	MakePath(n);
	reverse(path.begin(), path.end());

	for (int i = 1; i < path.size(); i++)
	{
		int u = path[i - 1];
		int v = path[i];

		edge.push_back(make_pair(min(u, v), max(u, v))); //최단경로의 간선을 저장한다
	}

	cout << Solve(1);

	return 0;
}