[13907] 세금

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

13907번: 세금

<문제>

다소 구현이 까다로운데, 정해를 떠올리기 위해 필요한 관찰은 어렵지 않다.

시작 정점 S에서 도착 정점 E까지 지나간 간선의 개수를 알고 있다면,

다익스트라를 다시 돌리거나 인접리스트를 건드리지 않아도 O(1)만에 세금을 적용한 비용을 알 수 있다.

시작에는 최적해였던것이 세금을 적용한 후에는 최적해가 아닐 수 있으므로, S를 제외한 집합에 대해서

모든 경로를 다 저장해둘 필요가 있겠다. 그렇기에 기존의 다익스트라에서 dist[]를 dist[][]로 확장하여

dist[i][j] : i번 정점을 j개의 간선을 지났을때의 최소비용으로 채워준다.

 

다익스트라는 전체에서 한번만 호출하고, 인접리스트도 입력에서만 유일하게 수정하며

각 쿼리마다 dist[e][1...N]을 순회하여 최소값을 찾음으로써, 쿼리당 O(N)으로 해를 구할 수 있다.

가령 dist[e][6]을 참조할때에는, score = 6*tax + dist[e][6]으로 계산하여 세금적용 후 비용을 찾는다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
using pi = pair<int, int>;
using ll = long long;
vector<pi> adj[1001];
int dist[1005][1005];
int n, m, k, s, e;
struct state {
    int node, cost, cnt;
};
struct cmp {
    bool operator()(state& a, state& b) { return a.cost > b.cost; }
};
void f(void) {
    int i, j;
    for (i = 1; i <= 1000; i++) {
        for (j = 1; j <= 1000; j++) {
            dist[i][j] = INF;
        }
    }
    dist[s][0] = 0;
    priority_queue<state, vector<state>, cmp> q;
    q.push({s, 0, 0});
    while (!q.empty()) {
        auto cur = q.top();
        q.pop();
        if (cur.cost > dist[cur.node][cur.cnt]) continue;
        for (auto& next : adj[cur.node]) {
            int nCost = next.first;
            int nNode = next.second;
            if (dist[nNode][cur.cnt + 1] > cur.cost + nCost) {
                dist[nNode][cur.cnt + 1] = cur.cost + nCost;
                q.push({nNode, cur.cost + nCost, cur.cnt + 1});
            }
        }
    }
    return;
}
int solve(int tax) {
    int i, ans = INF;
    for (i = 1; i <= 1000; i++) {
        ll score = ((ll)i * (ll)tax) + (ll)dist[e][i];
        if (score <= INT_MAX) ans = min((int)score, ans);
    }
    return ans;
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    cin >> s >> e;
    int i, j;
    for (i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    f();
    cout << solve(0) << '\n';
    int x = 0, taxPsum = 0;
    while (k--) {
        cin >> x;
        taxPsum += x;
        cout << solve(taxPsum) << '\n';
    }
    return 0;
}