백준9866 Vacation Planning

작성일 | In

문제 링크

  • http://icpc.me/9866

문제 출처

  • 2013 USACO December Gold 1번

사용 알고리즘

  • 다익스트라

시간복잡도

  • $O(MK \log N + KQ)$

풀이

허브의 개수 $K$가 작으므로, (어떤 정점에서 각 허브로 가는 최소 비용)과 (각 허브에서 다른 정점으로 가는 최소 비용)을 각각 전처리하면 된다는 생각을 해볼 수 있습니다.
이 값들을 알고 있으면 (시작점에서 어떤 허브로 가는 최소 비용) + (어떤 허브에서 끝점으로 가는 최소 비용) 중 최솟값이 정답이 됩니다.

각 허브에서 다른 정점으로 가는 최소 비용은 단순히 다익스트라 알고리즘을 $K$번 돌리면 됩니다. 마찬가지로, 어떤 정점에서 각 허브로 가는 것은 그래프의 간선 방향을 반대로 뒤집고 다익스트라 알고리즘을 돌리면 됩니다.

$O(M \log N)$ 다익스트라를 $K$번 돌려서 전처리하면, 쿼리에 대한 정답은 $O(K)$만에 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

int N, M, K, Q, H[222];
vector<pll> G[20202], R[20202];
ll D[222][2][20202];

void Dijkstra(int st, vector<pll> *g, ll *dst){
    priority_queue<pll> pq;
    pq.emplace(0, st); dst[st] = 0;
    while(pq.size()){
        ll v = pq.top().y, c = -pq.top().x; pq.pop();
        if(c > dst[v]) continue;
        for(auto i : g[v]){
            if(dst[i.x] > dst[v] + i.y){
                dst[i.x] = dst[v] + i.y;
                pq.emplace(-dst[i.x], i.x);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K >> Q;
    for(int i=1; i<=M; i++){
        ll s, e, x; cin >> s >> e >> x;
        G[s].emplace_back(e, x);
        R[e].emplace_back(s, x);
    }
    for(int i=1; i<=K; i++) cin >> H[i];

    memset(D, 0x3f, sizeof D);
    for(int i=1; i<=K; i++) Dijkstra(H[i], G, D[i][0]), Dijkstra(H[i], R, D[i][1]);

    ll cnt = 0, sum = 0;
    for(int i=1; i<=Q; i++){
        int s, e; cin >> s >> e;
        ll mn = 0x3f3f3f3f3f3f3f3f;
        for(int j=1; j<=K; j++) mn = min(mn, D[j][1][s] + D[j][0][e]);
        if(mn < 1e18) cnt++, sum += mn;
    }
    cout << cnt << "\n" << sum;
}