题目链接

题意

给定一个\(N\)个点的无向图，求从任意一个点出发，经过所有点的最短路径长度（每个点至多可以经过两次）。

思路

状态表示、转移及大体思路 与 poj 3311 Hie with the Pie 经过所有点(可重)的最短路径 floyd + 状压dp 相同。

但，因为是每个点 至多可以经过两次，所以应该用 三进制 来表示状态。

因为三进制不能直接通过移位来表示，所以要 预处理 出每个数字\(state\)的三进制表示中每一位\(i\)上的值\(dig[state][i]\).

注意：该题数据中有重边。

Code

#include <bits/stdc++.h>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

#define inf 0x3f3f3f3f

#define maxs 60010

#define maxn 12

using namespace std;

typedef long long LL;

int power3[] = {1, 3, 9,27,81,243,729,2187,6561,19683,59049};

int n, m, dp[maxs][maxn], dig[maxs][maxn], dis[maxn][maxn];

bool vis[maxs][maxn];

void init() {

    F(i, 0, power3[n]) {

        int state = i, cnt = 0;

        while (state) {

            dig[i][cnt++] = state%3;

            state /= 3;

        }

    }

}

int dfs(int state, int p) {

    if (state == power3[p]) return 0;

    if (vis[state][p]) return dp[state][p];

    vis[state][p] = true;

    int sta = state - power3[p], ans = inf;

    F(i, 0, n) {

        if (dis[i][p] && dig[state][i] && (i!=p || (i==p&&dig[state][i]==2))) ans = min(ans, dfs(sta, i)+dis[i][p]);

    }

    return dp[state][p] = ans;

}

inline bool check(int state) {

    F(i, 0, n) if (!dig[state][i]) return false;

    return true;

}

void work() {

    memset(dp, 0, sizeof dp); memset(vis, 0, sizeof vis); memset(dis, 0, sizeof dis);

    init();

    F(i, 0, m) {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w); --u, --v;

        if (dis[u][v]==0 || w<dis[u][v]) dis[u][v] = dis[v][u] = w;

    }

    int lim = power3[n]-1, ans = inf;

    F2(i, lim>>1, lim) {

        if (!check(i)) continue;

        F(j, 0, n) {

            ans = min(ans, dfs(i, j));

        }

    }

    printf("%d\n", ans==inf?-1:ans);

}

int main() {

    while (scanf("%d%d", &n,&m) != EOF) work();

    return 0;

}

巴特西

hdu 3001 Travelling 经过所有点(最多两次)的最短路径三进制状压dp

题目链接

题意

思路

Code

最新文章

热门文章

巴特西

hdu 3001 Travelling 经过所有点(最多两次)的最短路径 三进制状压dp

题目链接

题意

思路

Code

最新文章

热门文章

hdu 3001 Travelling 经过所有点(最多两次)的最短路径三进制状压dp