[백준/BOJ] 13907 세금 C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/13907

[설명]
다익스트라를 통해서 최소한의 통행료를 써서 이동하는 경로를 구할 수 있다. 이때, 세금 인상 시에는 도로의 개수도 중요하게 고려해야 하므로 도로의 개수별로 구해주면 된다. 그리고 어떤 정점으로의 최적 경로에 대하여 지나온 도로의 개수와 통행료를 저장해놓아야 한다. 만약 도로의 개수도 많고 통행료도 더 크다면 이 경로를 추가로 저장해줄 이유가 없다. 즉, 세금 인상 시에 대한 답일 가능성이 없다는 것이다.

이후 세금을 입력받고 각각의 경우에 대한 답을 출력하면 된다.

[코드]

#include<iostream>
#include<queue>
#include<vector>
#define INF 33000001
using namespace std;

struct info {
	int x, dis, cnt;
};

struct g_info {
	int x, dis;
};

struct cmp {
	bool operator()(const info& a, const info& b) {
		return a.dis > b.dis;
	}
};

priority_queue<info, vector<info>, cmp> pq;
vector<g_info> graph[1001];
int N, M, K, start_, end_, dis_with_cnt[1001][1001], dist[1001][2];

void dijkstra() {
	pq.push({ start_,0,0 });
	int x, dis, cnt;
	while (!pq.empty()) {
		x = pq.top().x;
		dis = pq.top().dis;
		cnt = pq.top().cnt;
		pq.pop();
		if (dis > dis_with_cnt[cnt][x]) continue;
		for (auto& iter : graph[x]) {
			if (dist[iter.x][0] < cnt + 1 && dist[iter.x][1] < dis + iter.dis) continue;
			if (dis_with_cnt[cnt + 1][iter.x] > dis + iter.dis) {
				dis_with_cnt[cnt + 1][iter.x] = dis + iter.dis;
				pq.push({ iter.x,dis_with_cnt[cnt + 1][iter.x],cnt + 1 });
				if (dist[iter.x][1] > dis + iter.dis) {
					dist[iter.x][1] = dis + iter.dis;
					dist[iter.x][0] = cnt + 1;
				}
			}
		}
	}
}

void init() {
	int i, j;
	for (i = 0; i <= N; i++) {
		if (i == start_) continue;
		for (j = 0; j <= N; j++) dis_with_cnt[j][i] = dist[j][0] = dist[j][1] = INF;
	}
}

void input() {
	int a, b, c;
	while (M--) {
		cin >> a >> b >> c;
		graph[a].push_back({ b,c });
		graph[b].push_back({ a,c });
	}
}

void solve() {
	int tax, i, ans = INF;
	for (i = 1; i <= N; i++) {
		if (dis_with_cnt[i][end_] == INF) continue;
		ans = min(ans, dis_with_cnt[i][end_]);
	}
	cout << ans << '\n';
	while (K--) {
		cin >> tax;
		ans = INF;
		for (i = 1; i <= N; i++) {
			if (dis_with_cnt[i][end_] == INF) continue;
			dis_with_cnt[i][end_] += i * tax;
			ans = min(ans, dis_with_cnt[i][end_]);
		}
		cout << ans << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> K >> start_ >> end_;
	input();
	init();
	dijkstra();
	solve();
}