Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 Orienteering

Category: JOI Tag: dp, topological-sort

Orienteering

問題概要


始点1, 終点nで頂点1からどの頂点にも到達可能なDAGが与えられる.
K個の頂点をチェックポイントとして指定する.
2人であわせて全てのチェックポイントを通って始点から終点に向かうようなパスの最短距離を求めよ

解法


まずどの頂点がどの頂点より前に来るか知りたいのでトポロジカルソートする.
続いてチェックポイント以外で止まることに意味はないので, チェックポイントだけのグラフを考えて全点対最短路を求める.
あとはどのように頂点を進んでいくか.

片方がどちらかより先行していて, かつその頂点までのトポロジカル順で前にあるチェックポイントは全て通っているとする.
このときの頂点をそれぞれ順にv, uと置く. またその状態までの最短距離をdp[v][u]と置く.
そうすると次に向かう頂点wはvのトポロジカル順で次のチェックポイントになる.
wにはどちらが進んでも問題ないが先行する方を次のvにするということに注意する.

これに加えてどちらも先行しない, つまりどちらも同じ場所にいる場合も考える.
これは先行する場合の遷移先と, 先行する場合の遷移元に同じ頂点にいる場合を付け加えるだけで良い.

コード


(orienteering.cpp) download
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int inf = 1e9;

int n, m, k, chk[1024], done[1024], rev[1024], d[1024][1024], dp[1024][1024];
vector<pii> G[1024];
vector<int> vs, ps;

inline void chmin(int &a, int b){a=min(a,b);}

void topo_dfs(int v)
{
        if(done[v]) return;
        done[v] = 1;
        for(auto &e: G[v]) topo_dfs(e.first);
        vs.push_back(v);
}

void topological_sort()
{
        topo_dfs(0);
        reverse(begin(vs),end(vs));
}

void dijkstra(int s)
{
        priority_queue<pii, vector<pii>, greater<pii>> q;
        q.push(pii(0,s));
        while(!q.empty()) {
                int v = q.top().second, c = q.top().first;
                q.pop();
                if(d[s][v] < inf) continue;
                d[s][v] = c;
                for(auto &e: G[v]) q.push(pii(c+e.second,e.first));
        }
}

int solve()
{
        topological_sort();
        for(auto &v: vs) {
                if(!chk[v]) continue;
                fill(d[v],d[v]+n,inf);
                fill(dp[v],dp[v]+n,inf);
                ps.push_back(v);
                dijkstra(v);
        }
        ps.push_back(n);

        dp[0][0] = 0;
        for (int i = 0; i < k; i++) {
                int &v = ps[i], &w = ps[i+1];
                d[v][v] = 0;
                for (int j = 0; j <= i; j++) {
                        int &u = ps[j];
                        chmin(dp[w][u], dp[v][u]+d[v][w]);
                        chmin(dp[w][v], dp[v][u]+d[u][w]);
                        chmin(dp[v][v], dp[v][u]+d[u][v]);
                }
        }
        return dp[n-1][n-1];
}

void input()
{
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
                cin >> chk[i];
                if(!i or i==n-1) chk[i] = 1;
                k += chk[i];
        }
        int a, b, c;
        for (int i = 0; i < m; i++) {
                cin >> a >> b >> c;
                G[a-1].push_back(pii(b-1,c));
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments