[Dijkstra] BOJ 13907 세금

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

13907번: 세금

문제에서 제시된, "세금이 인상될 때 최단거리가 갱신되는 경우"란 무엇일까?

세금이 인상되지 않았을 때 최단거리를 이미 알고 있다는 가정에서 생각해보자.

 

① 세금이 인상될 때, 어떤 한 경로에 대해 비용의 상승은 무엇에 의해 결정될까?

이는 해당 경로에 포함된 간선의 개수와 관련된다. 즉, 세금이 k원 인상될 때, 간선을 m개 포함한 경로는 총 m * k의 세금이 인상되는 것과 같다.

 

② 그렇다면 기존 최단경로보다 더 가중치가 작아지는 경우는?

d1, d2, d3은 각각 세금 인상 전의 경로 가중치 합이다.

세금이 인상되지 않았을 때의 기존 최단경로에 대해, 이 최단경로보다 더 많은 간선을 가지는 경로는 절대로 기존 최단경로보다 가중치 합이 작아질 수 없다. 이미 경로의 가중치 합이 최단경로보다 크기 때문이다.

따라서, 세금이 인상되었을 때 기존 최단경로보다 가중치가 작아질 수 있는 후보 경로는, 기존 최단경로의 간선 수보다 더 적은 간선을 포함하는 모든 경로이다.

 

③ 그렇다면 최단경로보다 더 적은 간선을 갖는 경로들을 어떻게 찾을 수 있을까?

이 풀이에서는 dist 배열의 차원을 하나 더 높이는 방법을 사용했다.

즉, dist[i][j] 의 형태로 두어 i번 노드까지의 j개의 간선을 통해 도착했을 경우 최단경로를 저장하도록 한다.

이후 도착 노드에 대해 각 세금 인상을 구현하여 적용하면 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
#define INF 999999999
#define INFL 99999999999
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n, m, k, s, d;
int dist[1001][1001];
vector<int> tax;
vector<pair<ll, int>> fin_dist;        //도착지점까지의 가중치 합과 지나온 간선의 갯수를 저장
vector<p> adj[1001];
 
void dijkstra() {
    //최단경로를 구하고 지나온 간선의 갯수를 구해 상한선을 정한다.
    priority_queue<pair<int, p>> pque;
    pque.push({ 0, { s, 0 } });
    dist[1][1] = 0;
 
    while (!pque.empty()) {
        pair<int, p> cur = pque.top();
        pque.pop();
 
        int distval = -cur.first;
        int node = cur.second.first;
        int ecnt = cur.second.second;
 
        if (ecnt == n) continue;
 
        if (dist[node][ecnt] >= distval) {
            for (int i = 0; i < adj[node].size(); i++) {
                int nextnode = adj[node][i].first;
                int newDist = distval + adj[node][i].second;
 
                if (dist[nextnode][ecnt + 1] > newDist) {
                    dist[nextnode][ecnt + 1] = newDist;
                    pque.push({ -newDist, { nextnode, ecnt + 1 } });
                }
            }
        }
    }
}
 
void init() {
    int a, b, w, p;
    cin >> n >> m >> k;
 
    cin >> s >> d;
 
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> w;
        adj[a].push_back({ b, w });
        adj[b].push_back({ a, w });
    }
 
    for (int i = 0; i < k; i++) {
        cin >> p;
        tax.push_back(p);
    }
 
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            dist[i][j] = INF;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    dijkstra();
 
    int min_ecnt = n, fastest = INF;
 
    //최단경로의 간선 수 찾기
    for (int i = 1; i <= n; i++) {
        if (dist[d][i] == INF) continue;
        if (dist[d][i] < fastest) { fastest = dist[d][i]; min_ecnt = i; }
    }
 
    //최단경로 간선보다 적은 간선을 갖는 경로만 추려냄
    for (int i = 1; i <= min_ecnt; i++) {
        if (dist[d][i] == INF) continue;
        fin_dist.push_back({ (ll)dist[d][i], i });
    }
 
    ll result = INFL;
    printf("%d\n", fastest);
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < fin_dist.size(); j++) {
            fin_dist[j].first += (ll)tax[i] * fin_dist[j].second;
            result = min(result, fin_dist[j].first);
        }
        printf("%lld\n", result);
        result = INFL;
    }
 
    return 0;
}