BOJ 13907 - 세금 [C++]

문제

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

 

간선의 가중치가 시간 $t$에 대한 일차함수의 형태인 무방향 그래프와, 정수 $s, e$가 주어진다.

특정 시간 $t$에서, $s$에서 $e$로 가는 최단 거리를 구해야 한다.

 

풀이

최단 경로에는 어떠한 경우에도 같은 간선이 두 번 이상 포함되지 않는다. 즉, 최대 $N-1$개의 간선만을 지난다.

따라서 다음과 같은 정의를 쉽게 떠올릴 수 있다.

• $dist[n][k]$는 $s$번 도시에서 $n$번 도시까지 $k$개의 간선을 지나서 갔을 때의 최단 거리

이제 그대로 다익스트라를 돌려주고, 쿼리가 주어질 때마다 $psum += p$ 후에 $\min(dist[e][j] + j \times psum)$을 출력하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int N, M, K, s, e;
    cin>>N>>M>>K>>s>>e;

    vector<vector<pair<int, int>>> V(1001);
    for(;M--;){
        int a,b,c;
        cin>>a>>b>>c;
        V[a].emplace_back(b,c);
        V[b].emplace_back(a,c);
    }

    vector<vector<int>> D(1001, vector<int>(1000, -1));
    D[s][0] = 0;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> Q;
    Q.emplace(0,s,0);
    while(!Q.empty()){
        auto [dist, now, cross] = Q.top();
        Q.pop();
        if(dist > D[now][cross])    continue;
        for(auto &[next, cost] : V[now]){
            int res = dist + cost;
            if(D[next][cross+1] == -1 || D[next][cross+1] > dist + cost){
                D[next][cross+1] = dist + cost;
                Q.emplace(D[next][cross+1], next, cross+1);
            }
        }
    }
    
    int S = 0;
    int ans = 1e9;
    for(int i=0;i<1000;i++){
        if(D[e][i] == -1)   continue;
        ans = min(ans, D[e][i] + i*S);
    }
    cout<<ans<<'\n';
    for(;K--;){
        int a;
        cin>>a;
        S += a;
        ans = 1e9;
        for(int i=0;i<1000;i++){
            if(D[e][i] == -1)   continue;
            ans = min(ans, D[e][i] + i*S);
        }
        cout<<ans<<'\n';
    }

}