[백준 13907번] [Dijkstra / DP] 세금

Approach

아마 다익스트라 문제임은 쉽게 파악할 수 있을 것이다.

이 문제를 풀기위해 가장 중요한 점은, 각 경로 별로 통행료와 간선의 개수를 파악하는 것이다. 왜냐하면, 통행료가 올라감에 따라 간선의 개수가 많을수록 통행료가 증가하기 때문이다.

 

즉, 간선의 개수 별로 최소 통행료를 구하는 것이 필요하고 이를 DP느낌으로 처리해주면 된다.

dist[i][j] : 출발점에서 정점 i까지 j만큼의 간선을 통과했을 때의 최소 통행료

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef tuple<int, int, int> tiii;
typedef long long ll;
typedef vector <ull> ullv1;
typedef vector <vector <ull> > ullv2;
const int INF = 500000000;


int main() {
    fastio;
    int n, m, k, s, d;
    cin >> n >> m >> k >> s >> d;
    s--;
    d--;

    vector<pii> edge[n];
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edge[a - 1].push_back({b - 1, c});
        edge[b - 1].push_back({a - 1, c});
    }

    int dist[1000][1000];
    fill(&dist[0][0], &dist[999][1000], INF);
    priority_queue<tiii, vector<tiii>, greater<tiii> > pq; // cost, point, length
    
    pq.push({0, s, 0});
    dist[s][0] = 0;

    while(!pq.empty()){
        int cur_cost, cur, length;
        tie(cur_cost, cur, length) = pq.top();
        pq.pop();

        if(dist[cur][length] < cur_cost || length >= n) continue; // 제거
        
        for(auto p : edge[cur]){
            int to = p.first, cost = p.second;
            if(cur_cost + cost < dist[to][length + 1]){
                dist[to][length + 1] = cur_cost + cost;
                pq.push({dist[to][length + 1], to, length + 1});
            }  
        }
    }

    int min_num = INF;

    for(int i = 1; i < n; i++){
        min_num = min(min_num, dist[d][i]);
    }
    cout << min_num << "\n";

    int mul = 0;

    for(int i = 0; i < k; i++){
        int t;
        cin >> t;
        mul += t;
        min_num = INF;
        for(int j = 1; j < n; j ++){
            min_num = min(min_num, dist[d][j] + mul * j);
        }
        cout << min_num << "\n";
    }
    return 0;
}