[백준] 2307 - 도로검문

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

2307번: 도로검문

 

이 문제에서 모든 M개의 간선에 대해 제외하고 다익스트라를 돌리게 되면, O(MNlogM) -> TLE가 날 수 있다.

따라서 시간 최적화를 진행해야 한다.

잘 생각해 보면, 용의자가 1번 정점에서 n번 정점까지 가는 데에 쓰인 간선 중에서만 검문을 거치면 된다. 그 외 간선에서는 검문을 해봤자, 최단 거리에 영향을 주지 않기 때문이다.

그렇다면 최단 거리에 쓰인 간선을 어떻게 판단할 수 있을까?

본인은 parent 배열을 이용해 최단 거리가 갱신될 때 node, nextNode를 이용해서 parent[nextNode] = node 이런 식으로 다음 정점을 가리켜 주었다.

 

그래서 parent[n] 부터, parent[x] = 1까지 간선을 제외해 다익스트라를 돌렸다.

 

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

int n, m, ok;
vector<vector<pair<int, int>>> v;
int parent[1001];

int dijk(int a, int b)
{
	vector<int> dis(n + 1, 987654321);
	priority_queue<pair<int, int>> pq;

	dis[1] = 0;
	pq.push({0, 1});

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

		if (dis[node] < cost)
			continue;

		for (auto &i : v[node])
		{
			if (ok && ((node == a && i.first == b) || (node == b && i.first == a)))
			{
				continue;
			}
			int nxNode = i.first;
			int nxCost = cost + i.second;
			if (dis[nxNode] > nxCost)
			{
				if (!ok)
				{
					parent[nxNode] = node;
				}
				pq.push({-nxCost, nxNode});
				dis[nxNode] = nxCost;
			}
		}
	}

	ok = 1;

	if (dis[n] == 987654321)
	{
		return -1;
	}

	return dis[n];
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	v.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
	}
	int dis = dijk(-1, -1);
	int ans = -1;
	for (int i = n; i != parent[i]; i = parent[i])
	{
		int t = dijk(i, parent[i]);
		if (t == -1)
		{
			ans = -1;
			break;
		}
		ans = max(ans, t - dis);
	}

	cout << ans;
}