Algoogle

Algorithm for Programming Contest

AOJ 2567 SIRO Challenge

Category: AOJ Tag: dp, warshall-floyd

SIRO Challenge

問題概要


解法


ラーメン屋がある駅だけに注目すればいいのでWarshall-Floydでラーメン屋間の最短距離を求めておく.
あとはTSPの全部回らなくてもいい場合みたいにbitDPする.
dp[S][v] = すでに行ったラーメン屋の集合Sで, 最後に行った店がvの時の最小の経過時間
dpの初期化はdp[0][s] = 0と各ラーメン屋iについてdp[1« i][s] = sとiの最短距離+食事時間
あとはbitDPするだけ.
結果は, 最後にsに行っていて, かつ時間がt以内であるSのうち, ビットが一番立ってる数をみればよい.
最後に-1してるのは簡単にするためにsも食事時間0のラーメン屋にしているのでそれを省くため.

コード


(2567.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
#include <iostream>

#define int long long
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define INF 1e9

using namespace std;

int n, m, l, s, t;
int wf[310][310], jiro[310], id[20], dp[1<<17][20];

bool input(){
    cin >> n >> m >> l >> s >> t;
    s--;
    if(!n) return 0;
    rep(i,n) rep(j,n) wf[i][j] = INF;
    rep(i,m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        wf[a][b] = c;
        wf[b][a] = c;
    }
    rep(i,l) {
        int j, e;
        cin >> j >> e;
        jiro[i] = e;
        id[i] = j-1;
    }
    jiro[l] = 0;
    id[l] = s;
    return 1;
}

int solve(){
    rep(k,n) rep(i,n) rep(j,n)
        wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]);

    rep(S,1<<(l+1)) rep(j,l+1) dp[S][j] = INF;
    dp[0][l] = 0;
    rep(i,l) dp[1<<i][i] = wf[s][id[i]] + jiro[i];

    repi(S,1,1<<(l+1)) rep(v,l+1) if(!((S >> v) & 1))
        rep(u,l+1) if((S >> u) & 1)
            dp[S | (1 << v)][v] = min(dp[S|(1<<v)][v], dp[S][u] + wf[id[u]][id[v]] + jiro[v]);

    int ans = 0;
    rep(S, 1<<(l+1)) if(dp[S][l] <= t)
        ans = max(ans, (int)__builtin_popcount(S) - 1);

    return ans;
}

signed main(){
    while(input()){ cout << solve() << endl;}
    return 0;
}

Comments