Algoogle

Algorithm for Programming Contest

AOJ 2200 Mr. Rito Post Office

Category: AOJ Tag: dp, warshall-floyd

Mr. Rito Post Office

問題概要


解法


最初に陸路を使う場合のみと海路を使う場合のみのそれぞれの全点対最短路を求める.
また, 入力では
“ある2つの町や村を直接結ぶ陸路または海路が2本以上存在することがある”
ので最小のものを選ぶ.

あとはDP
dp[i][k] = dp[i-1][j] + 陸路[z[i-1]][j] + 海路[j][k] + 陸路[k][z[i]]
また, j=kのときはそこに寄る必要はないのは明らかなのでそのときは
dp[i][j] = dp[i-1][j] + 陸路[z[i-1]][z[i]]
で求める.

コード


(2200.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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define pb push_back
#define INF 1e9
typedef vector<int> vi;

int n, m, r;
int dl[256][256], ds[256][256];
int dp[1024][256];
vi z;

void init(){
    z.clear();
    rep(i,256)rep(j,256){
        dl[i][j] = INF;
        ds[i][j] = INF;
    }
    rep(i,1024)rep(j,256) dp[i][j] = INF;
    return;
}

void input(){
    int x, y, t;
    char sl;
    rep(i,m){
        cin >> x >> y >> t >> sl;
        x--; y--;
        if(sl == 'L'){
            dl[x][y] = min(dl[x][y], t);
            dl[y][x] = min(dl[y][x], t);
        }else {
            ds[x][y] = min(ds[x][y], t);
            ds[y][x] = min(ds[y][x], t);
        }
    }
    cin >> r;
    rep(i,r){
        cin >> t;
        t--;
        z.pb(t);
    }
    return;
}

void solve(){
    rep(k,n)rep(i,n)rep(j,n){
        if(i==j){
            dl[i][j] = 0;
            ds[i][j] = 0;
        }
        dl[i][j] = min(dl[i][j], dl[i][k] + dl[k][j]);
        ds[i][j] = min(ds[i][j], ds[i][k] + ds[k][j]);
    }
    rep(i,n) dp[0][i] = ds[z[0]][i] + dl[i][z[0]];
    repi(i,1,r){
        rep(j,n)rep(k,n){
            if(j!=k)dp[i][k] = min(dp[i][k],
                                   dp[i-1][j]+dl[z[i-1]][j]+ds[j][k]+dl[k][z[i]]);
            else dp[i][j] = min(dp[i][j],
                                dp[i-1][j]+dl[z[i-1]][z[i]]);
        }
    }
    int ans = INF;
    rep(i,n) ans = min(ans, dp[r-1][i]);
    cout << ans << endl;
    return;
}

int main(){
    while(cin >> n >> m, n||m){
        init();
        input();
        solve();
    }
}

Comments