Algoogle

Algorithm for Programming Contest

AOJ 2672 Rescue a Postal Worker

Category: AOJ Tag: dijkstra, dp

Rescue a Postal Worker

問題概要


n(<=1000)頂点の無向グラフがある.
pから始めて,k(<=6)箇所に落ちている手紙をそれぞれk箇所の指定された家に届けるとき,すべて配り終えるまでの最短の時間を求めよ.

解法


手紙が落ちている場所と届ける家以外はいらないので,それら+始点の間の距離をDijkstraで求めておく.
それらの間でbitDPする.
dp[i][j] := すでに訪れた頂点集合iでjにいるときの最短時間
届け先には手紙を拾ってからじゃないとダメなように遷移させればよい.

コード


(2672.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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,n) repi(i,0,n)

inline void chmin(int &x, int y) { x = ~x? min(x,y): y; }

struct node {
    int v, d;
    node(int v, int d):v(v),d(d){}
    bool operator<(const node &n)const{ return d > n.d;}
};

const int MAX = 1024;
struct edge{ int to, d; };
vector<edge> G[MAX];
int dist[MAX][MAX];

void dijkstra(int s) {
    memset(dist[s], -1, sizeof(dist[s]));
    priority_queue<node> q;
    q.push(node(s, 0));
    while(!q.empty()){
        int v = q.top().v, d = q.top().d;
        q.pop();
        if(~dist[s][v] and dist[s][v] <= d) continue;
        dist[s][v] = d;
        for(int i = 0; i < (int)G[v].size(); i++)
            q.push(node(G[v][i].to, d+G[v][i].d));
    }
}

int n, m, k, p, s[1024], t[1024], d[16][16], dp[1<<12][16];

void solve()
{
    dijkstra(p);
    rep(i,k) {
        dijkstra(s[i]);
        dijkstra(t[i]);
    }

    memset(d,-1,sizeof(d));
    memset(dp,-1,sizeof(dp));
    m = 2*k;
    rep(i,k) repi(j,i,k) {
        d[i][j] = d[j][i] = dist[s[i]][s[j]];
        d[i][j+k] = d[j+k][i] = dist[s[i]][t[j]];
        d[i+k][j] = d[j][i+k] = dist[t[i]][s[j]];
        d[i+k][j+k] = d[j+k][i+k] = dist[t[i]][t[j]];
    }
    rep(i,k) dp[1<<i][i] = dist[p][s[i]];

    rep(i,1<<m) rep(j,m) if(~dp[i][j])
        rep(l,m) if(~d[j][l] and (l < k or (i>>(l-k))&1))
            chmin(dp[1<<l|i][l], dp[i][j]+d[j][l]);
    int ans = -1;
    rep(i,m) chmin(ans, dp[(1<<m)-1][i]);

    if(~ans) printf("%d\n", ans);
    else puts("Cannot deliver");
}

void input()
{
    scanf("%d%d%d%d", &n, &m, &k, &p);
    p--;
    rep(i,m) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        a--; b--;
        G[a].push_back((edge){b,c});
        G[b].push_back((edge){a,c});
    }
    rep(i,k) {
        scanf("%d%d", s+i, t+i);
        s[i]--; t[i]--;
    }
}

int main()
{
    input();
    solve();
    return 0;
}

Comments