BOJ #13907 세금

 

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

13907번: 세금

특정 정점을 방문하는 최단 경로를 구하는 문제이지만, 각 간선들의 통행료를 인상함에 따라 최단 경로가 변경될 수 있음에 유의해야 합니다.

 

dist[i][j] :: 시작 정점으로부터 i번 정점에 도착하기까지 j개의 간선을 이용했을 때의 최소 비용

 

#include <bits/stdc++.h>
using namespace std;
#define MX 1001
typedef pair<int, int> pii;
 
int n, m, k, S, E, dist[MX][MX], ans, sum;
vector <pii> vc[MX], v;
 
void func() {
    priority_queue <pair<int, pii>> pq;
    dist[S][0] = 0;
    pq.push({ 0, {0, S} });
    while (!pq.empty()) {
        auto x = pq.top(); pq.pop();
        int here = x.second.second;
        int cnt = x.second.first;
        int cost = -x.first;
        bool shorter = false;
        for (int i = 0; i < cnt; i++) {
            if (dist[here][i] < cost) {
                shorter = true;
                break;
            }
        }
        if (shorter || dist[here][cnt] < cost)
            continue;
        if (here == E) {
            ans = min(ans, dist[here][cnt]);
            continue;
        }
        for (auto y : vc[here]) {
            int next = y.first;
            int nextcost = y.second;
            if (cnt + 1 <= n && dist[next][cnt + 1] > dist[here][cnt] + nextcost) {
                dist[next][cnt + 1] = dist[here][cnt] + nextcost;
                pq.push({ -dist[next][cnt + 1], {cnt + 1, next} });
            }
        }
    }
}
 
int main() {
    scanf("%d%d%d%d%d", &n, &m, &k, &S, &E);
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        vc[a].push_back({ b, c });
        vc[b].push_back({ a, c });
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dist[i][j] = 1e9;
    ans = 1e9;
    func();
    printf("%d\n", ans);
    for (int i = 0; i <= n; i++) {
        if (dist[E][i] != 1e9)
            v.push_back({i, dist[E][i]});
    }
    while (k--) {
        int p;
        scanf("%d", &p);
        sum += p;
        int ret = 1e9;
        for (auto a : v) {
            ret = min(ret, a.second + a.first * sum);
        }
        printf("%d\n", ret);
    }
}