[백준] 2982 - 국왕의 방문

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

2982번: 국왕의 방문

 

주어지는 고둘라가 지나가는 시간에 들리는 경로를 제외한 최단 거리를 구하는 문제이다.

그래서 고둘라가 지나가는 경로의 지나가는 시간을, pair<int, int> go[1001][1001]로 정해주었다.

따라서 pair<int, int> go[i][j]는 고둘라가 i에서 j까지 이동할 때, first = 출발하는 시간, second = 도착하는 시간으로 하였다.

이 부분까지는 쉽게 할 수 있다.

 

그렇다면 상근이가 배달할 때는 어떤 점을 고려해야할까?

바로 고둘라와 동선이 겹치는 경우에는 고둘라가 끝나는 시간에 출발하는 것으로 하면 된다.

따라서 다음 줄을 추가해 주었다.

if (go[node][i].first - k <= nxCost && go[node][i].second - k >= nxCost)
{
	nxCost = go[node][i].second - k;
}

사실 이 문제에서 k는 큰 역할을 하지 못한다. 단지 고둘라의 도착 시간을 k만큼 더 빨리 하는 것이라서 가중치에 k만 빼주면 된다.

 

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

int n, m, a, b, k, g;
pair<int, int> go[1001][1001];
vector<int> inp;
int v[1001][1001];

int main()
{
	cin >> n >> m >> a >> b >> k >> g;
	for (int i = 0; i < g; i++)
	{
		int in;
		cin >> in;
		inp.push_back(in);
	}
	for (int i = 0; i < m; i++)
	{
		int n1, n2, cost;
		cin >> n1 >> n2 >> cost;
		v[n1][n2] = cost;
		v[n2][n1] = cost;
	}
	int prev = 0;
	for (int i = 1; i < inp.size(); i++)
	{
		int n1 = inp[i - 1];
		int n2 = inp[i];
		go[n1][n2].first = prev;
		go[n2][n1].first = prev;
		go[n1][n2].second = prev + v[n1][n2];
		go[n2][n1].second = prev + v[n1][n2];
		prev += v[n1][n2];
	}

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

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

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

		if (dis[node] < cost)
		{
			continue;
		}

		for (int i = 1; i <= n; i++)
		{
			if (i == node || !v[node][i])
			{
				continue;
			}
			int nxNode = i;
			int nxCost = cost;
			if (go[node][i].first - k <= nxCost && go[node][i].second - k >= nxCost)
			{
				nxCost = go[node][i].second - k;
			}
			nxCost += v[node][i];
			if (dis[nxNode] > nxCost)
			{
				dis[nxNode] = nxCost;
				pq.push({-nxCost, nxNode});
			}
		}
	}
	
	cout << dis[b];
}