[백준/BOJ] 백준 1162번 : 도로포장

www.acmicpc.net/problem/1162

1162번: 도로포장

포장할 수 있는 도로의 개수를 스킵할 수 있는 도로의 개수라고 생각을 했다. 다익스트라를 이용해서 문제를 해결하였는데, result[위치][앞으로 포장할 수 있는 도로] = 최소 시간을 저장하였고, pq에 (-비용,(위치,앞으로 포장할 수 있는 도로))를 저장하였다. 그리고 다익스트라를 진행하며 포장할 수 있는 도로의 개수가 있을 때는 현재 here-there 도로 포장 하는것과 포장 안 하는 것 두 가지를 모두 고려하고, 포장할 수 있는 도로의 개수가 없을 때는 here-there 도로 포장 안 하는 것만 고려하였다. 목적지까지 최소 시간은 result[dest][i] 중 가장 작은 값을 구하였다.

 

코드

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

int n, m, k;
vector<pair<int, int>> adj[10001]; //시간,목적지 순으로 저장

long long Solve(int start, int dest)
{
	long long result[10001][21]; //result[위치][앞으로 포장할수 있는 도로] = 최소 시간

	for (int i = 0; i < 10001; i++)
		for (int j = 0; j < 21; j++)
			result[i][j] = numeric_limits<long long>::max();

	result[start][k] = 0;

	priority_queue<pair<long long, pair<int, int>>> pq; //(-비용,(위치,앞으로 포장할수 있는 도로)) 저장

	pq.push(make_pair(-0, make_pair(start, k)));

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

		if (result[here][here_can_skip] < here_cost)
			continue;

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

			if (here_can_skip > 0) //현재 here-there 도로 포장 하는것 고려
			{
				if (result[there][here_can_skip - 1] > here_cost)
				{
					result[there][here_can_skip - 1] = here_cost;
					pq.push(make_pair(-here_cost, make_pair(there, here_can_skip - 1)));
				}
			}

			if (result[there][here_can_skip] > there_cost) //현재 here-there 도로 포장 안하는것 고려
			{
				result[there][here_can_skip] = there_cost;
				pq.push(make_pair(-there_cost, make_pair(there, here_can_skip)));
			}

		}
	}

	long long ret = numeric_limits<long long>::max();

	for (int i = 0; i < 21; i++)
		ret = min(ret, result[dest][i]);

	return ret;
}

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

	cin >> n >> m >> k;

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

		cin >> u >> v >> t;

		adj[u].push_back(make_pair(t, v));
		adj[v].push_back(make_pair(t, u));
	}

	cout << Solve(1, n);

	return 0;
}