hdu3001（状态压缩DP）

hdu3001

题意

选择从任意一点出发，经过所有点的最小花费（经过每个点的次数不能多于 2 次）。

分析

类似于 poj3311

经过每个点的次数有限制，考虑用三进制数存储每个点被访问过的次数，其它和上面一题几乎相同。

code

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long ll;

const int MAXN = 60000;

const int INF = 1e9;

int dp[MAXN][12];

int dis[12][12];

int main() {

    int m, n;

    while(cin >> n >> m) {

        memset(dis, 0x3f, sizeof dis);

        memset(dp, 0x3f, sizeof dp);

        for(int i = 0; i < m; i++) {

            int x, y, c;

            cin >> x >> y >> c; x--; y--;

            dis[y][x] = dis[x][y] = min(c, dis[x][y]);

        }

        int total = 1;

        for(int i = 0; i < n; i++) {

            dis[i][i] = 0;

            total *= 3;

        }

        for(int i = 0; i < total; i++) {

            for(int j = 0; j < n; j++) {

                int s = i, add = 1;

                int t = j;

                while(t--) {

                    s /= 3;

                    add *= 3;

                }

                s %= 3;

                if(s < 2) {

                    dp[add][j] = 0; // 可以从任意一点出发

                    s = i;

                    for(int k = 0; k < n; k++) {

                        if(s % 3 > 0) {

                            dp[i + add][j] = min(dp[i + add][j], dp[i][k] + dis[k][j]);

                        }

                        s /= 3;

                    }

                }

            }

        }

        int ans = INF;

        for(int j = 0; j < n; j++) {

            ans = min(ans, dp[total - 1][j]);

        }

        if(ans == INF) ans = -1;

        cout << ans << endl;

    }

    return 0;

}

巴特西

hdu3001（状态压缩DP）

hdu3001

题意

分析

code

最新文章

热门文章