[백준/BOJ] 백준 13907번 : 세금

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

13907번: 세금

출발 도시에서 도착 도시로 최소비용으로 가는 것을 다익스트라를 이용해서 구하는데, 이때 몇 개의 간선을 지났는지에 따라 최소비용을 따로 구하는 방법으로 문제를 해결했다.

 

코드

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

int n, m, k;
int s, d;
vector<pair<int, int>> adj[1001]; //(비용, 목적지)
vector<int> output;
vector<vector<int>> short_value(1001, vector<int>(1000, 987654321)); //short_value[정점][몇개의 간선을 지났는지] = 최소 비용

void Dist(int start, int dest)
{
	priority_queue<pair<int, pair<int, int>>> pq; //(-비용,(지난 간선의 수, 정점))
	short_value[start][0] = 0;

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

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

		//지난 간선이 총 정점의 개수 이상이 될때
		if (here_passed >= n)
			continue;

		if (short_value[here][here_passed] < here_cost)
			continue;

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

			if (short_value[there][there_passed] > there_cost)
			{
				short_value[there][there_passed] = there_cost;
				pq.push(make_pair(-there_cost, make_pair(there_passed, there)));
			}
		}
	}
}

//오른 세금이 add일때 최소 통행료
int Solve(int add)
{
	int ret = 987654321;
	for (int i = 0; i <= n - 1; i++)
	{
		ret = min(ret, short_value[d][i] + (i*add));
	}
	return ret;
}

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

	cin >> n >> m >> k;
	cin >> s >> d;

	for (int i = 0; i < m; i++)
	{
		int a, b, w;
		cin >> a >> b >> w;

		adj[a].push_back(make_pair(w, b));
		adj[b].push_back(make_pair(w, a));
	}

	Dist(s, d);

	int result;

	int sum = 0;
	result = Solve(sum);
	output.push_back(result);

	for (int i = 0; i < k; i++)
	{
		int p;
		cin >> p;
		sum += p;

		result = Solve(sum);
		output.push_back(result);
	}

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

	return 0;
}