Algoogle

Algorithm for Programming Contest

PKU 2137 Cowties

Category: PKU Tag: dp

Cowties

問題概要


解法


始点(かつ終点)を決めて(すべて試す), そこから順にDPで最短を求めていく.
dp[i][j] := i 番目の牛の候補地 j にたどり着くための最小距離
TSPを思い浮かべるとよい.
違うところは順番が決まっているのと, 各地点に候補地が複数あること.
順番が決まっているのでTSPでの通った場所のビット列はいらない(最後に訪れた場所はいる).
あとは追加で各牛の候補地 j には前の牛のどの候補地から来るのがいいのか調べれば良い.
最後に決めた始点に戻るにはどれから戻ればいいのか調べる.

コード


(2137.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
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <vector>

using namespace std;

typedef complex<double> point;

const double inf = 1e6;

int N;
vector<point> p[128];
double dp[128][64];

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        int n; scanf("%d", &n);
        for(int j = 0; j < n; j++){
            double x, y;
            scanf("%lf%lf", &x, &y);
            p[i].push_back(point(x,y));
        }
    }

    int ans = int(inf*100);
    for(int s = 0; s < p[0].size(); s++){
        for(int i = 0; i <= N; i++)
            for(int j = 0; j < 64; j++)
                dp[i][j] = inf;
        for(int i = 0; i < p[1].size(); i++)
            dp[1][i] = abs(p[0][s] - p[1][i]);
        for(int i = 2; i < N; i++)
            for(int j = 0; j < p[i].size(); j++){
                if(!i) dp[i][j] = 0;
                else for(int k = 0; k < p[i-1].size(); k++)
                    dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(p[i][j]-p[i-1][k]));
            }
        for(int i = 0; i < p[N-1].size(); i++)
            ans = min(ans, int(100*(dp[N-1][i]+abs(p[0][s] - p[N-1][i]))));
    }
    printf("%d\n", ans);
    return 0;
}

Comments