백준 13907 - 세금(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13907

13907번: 세금

다익스트라를 통해 탐색할 때, N번 지점을 몇 번을 거쳐 방문하는지를 확인해야하는 문제였습니다.

세금을 인상한 횟수가 30,000회, N이 1,000개 이하이기에 다익스트라를 사용할 때, 세금을 인상하면서 탐색을 하면 무조건 시간초과가 됩니다.
따라서, 다익스트라는 한번만 사용하고 해당 값을 통해 다른 값을 도출해내는 방법을 사용해야 함을 알 수 있습니다.

세금을 얼마를 인상했는지 알기에, 세금을 인상한 뒤의 최소 값은 ‘인상하기 전의 값 + 이동 횟수 * 올린 세금’ 을 전부 비교한 값 중 가장 작은 값임을 알 수 있습니다.
그렇다면, 필요한 값은 인상하기 전의 D점까지의 탐색 값과 각각의 경우의 이동 횟수가 됩니다.

여기서 D점까지의 최대 이동 횟수를 알 수 있습니다. N의 범위가 1,000이하이니, 1000-1개가 최대 이동횟수 입니다.
따라서 N*N배열인 Distance[X][Y]를 만들어 ’X번을 Y번째로 왔을 때의 최소 값‘ 을 저장하면 됩니다.

탐색이 끝난 뒤, 해당 값을 이용해, 세금을 인상했을 때의 최솟값도 구해주면 됩니다.  


자세힌 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF LLONG_MAX
#define F first
#define S second

using namespace std;

int N, M, K;
int S, D;
vector<pair<int, int>> connect[1001];
int tax[30001];
long long Distance[1001][1001]; //위치, 위치까지 이동횟수
priority_queue<pair<long long, pair<int, int>>> q; //최소비용, 이동 횟수, 위치

void reset_distance(){
	for(int i = 1; i <= N; i++){
		for(int j = 0; j < N; j++){
			Distance[i][j] = INF;
		}
	}
}

void Dijstra(){
	Distance[S][0] = 0;
	q.push({-0, {0, S}});
	while(!q.empty()){
		int x = q.top().S.S;
		int cnt = q.top().S.F;
		long long cost = -q.top().F;
		q.pop();
		if(Distance[x][cnt] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			long long n_cost = cost + connect[x][i].S;
			if(Distance[xx][cnt+1] > n_cost){
				Distance[xx][cnt+1] = n_cost;
				q.push({-Distance[xx][cnt+1], {cnt+1, xx}});
			}
		}
	}
}

void solve(){
	reset_distance();
	Dijstra();
	for(int i = 0; i <= K; i++){
 		long long sum = INF;
		for(int j = 0; j < N; j++){
			if(Distance[D][j] == INF) continue;
			sum = min(sum, Distance[D][j] + j*tax[i]);
		}
		cout << sum << "\n";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	cin >> S >> D;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost);
		connect[x].push_back({y, cost});
		connect[y].push_back({x, cost});
	}
	for(int i = 1; i <= K; i++) {
		scanf("%d", &tax[i]);
		tax[i] += tax[i-1];
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.