플래4 - 백준 13907 세금

백준 13907 세금

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

접근방법

세금이 오르는 일차별로 거리에 따라 드는 비용이 다르기 때문에 가장 싼 경로로 도착지까지 가는데 거치는 거리를 구하고, 그 거치는 거리보다 짧고 싼 모든 도착지까지의 경로를 구해서 저장하고 일차별로 가장 싼 금액을 출력해주었다.

풀이

우선 다익스트라를 한번 실행해서 도착지까지의 가장 비용이 싼 경로를 찾고 그 경로를 이용할 때 거치는 길의 수를 cnt에 저장해주었다.
그리고 다시 한번 다익스트라를 실행시켜서 path_cnt별로 따로 최단 거리를 저장해주었다. 이때 path_cnt가 cnt와 같거나 큰 경우는 세금을 계산해주는 것이 의미 없으므로 continue 해주어 최적화 해주었다.
increase_tax 함수를 통해 일차별로 오르는 tax를 입력받고 비용을 갱신해주었고 그 중 최소 비용을 반환해주어 출력하였다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

vector<vector<int>> route;
int cost[1001][1001];
int visited[1001][1001];
int least_cost[1001];
int N, M, K;

int increase_tax(int tax, int end)
{
	int Min = -1;

	for (int i = 1; i < N; i++)
	{
		if (visited[end][i] == -1)
			continue;

		visited[end][i] += i * tax;

		if (Min == -1 || Min > visited[end][i])
			Min = visited[end][i];
	}

	return Min;
}

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

	memset(cost, -1, sizeof(cost));
	memset(visited, -1, sizeof(visited));
	memset(least_cost, -1, sizeof(least_cost));

	cin >> N >> M >> K;

	for (int i = 0; i <= N; i++)
	{
		vector<int> temp;
		route.push_back(temp);
	}

	int start, end;
	cin >> start >> end;

	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		route[a].push_back(b);
		route[b].push_back(a);

		if (cost[a][b] == -1 || cost[a][b] > c)
		{
			cost[a][b] = c;
			cost[b][a] = c;
		}
	}

	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	pq.push({ 0, { start, 0 } });
	least_cost[start] = 0;

	int cnt = 0;

	while (!pq.empty())
	{
		int cur = pq.top().second.first;
		int cur_cost = pq.top().first;
		int pass_cnt = pq.top().second.second;
		pq.pop();

		for (int i = 0; i < route[cur].size(); i++)
		{
			if (least_cost[route[cur][i]] == -1 || least_cost[route[cur][i]] > cur_cost + cost[cur][route[cur][i]])
			{
				least_cost[route[cur][i]] = cur_cost + cost[cur][route[cur][i]];
				pq.push({ cur_cost + cost[cur][route[cur][i]] , {route[cur][i], pass_cnt + 1} });
				if (route[cur][i] == end)
					cnt = pass_cnt + 1;
			}
		}
	}

	pq.push({ 0, { start, 0 } });
	visited[start][0] = 0;

	while (!pq.empty())
	{
		int cur = pq.top().second.first;
		int cur_cost = pq.top().first;
		int pass_cnt = pq.top().second.second;
		pq.pop();

		if (pass_cnt >= cnt)
			continue;

		for (int i = 0; i < route[cur].size(); i++)
		{
			if (visited[route[cur][i]][pass_cnt + 1] == -1 || visited[route[cur][i]][pass_cnt + 1] > cur_cost + cost[cur][route[cur][i]])
			{
				visited[route[cur][i]][pass_cnt + 1] = cur_cost + cost[cur][route[cur][i]];
				pq.push({ cur_cost + cost[cur][route[cur][i]] , {route[cur][i], pass_cnt + 1} });
			}
		}
	}

	cout << increase_tax(0, end) << '\n';

	while (K--)
	{
		int tax;
		cin >> tax;
		cout << increase_tax(tax, end) << '\n';
	}
}