ACM学习历程—HDU5418 Victor and World(动态规划 && 状压)

这个题目由于只有16个城市，很容易想到去用状压来保存状态。

p[i][state]表示到i城市经过state状态的城市的最优值（state的二进制位每一位为1表示经过了该城市，否则没经过）

这样p[j][state|(1<<i)] = min(p[i][state]+dis[i][j])了

方程出来了不会遍历，打BC的时候，一开始用dfs遍历T了一发。后来换成SPFA了，不过当时脑子昏了，竟然忘记对队列里的数进行判重了，不过终测竟然没过，去HDU上用G++交是可以AC的。。

可能是不判重，SPFA常数比较大，有点卡时间。

判重加上就好了。

看到最后题解先用Floyed得到了两点之间的最短路。先不管两点间经过多少个点。不过用上面的做法应该是不用这一步也可以的。

然后再dp方程。遍历需要先遍历state。

不管怎样先粘代码吧，下次再打上Div1吧。

代码：（spfa）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <string>
#include <algorithm>
#define LL long long

using namespace std;

typedef pair<int, int> pii;
int dis[20][20], n, m;
int vis[17][131100];
int p[17][131100];

inline int myMin(int now, int tmp)
{
    if (now == -1)
        return tmp;
    else
        return min(now, tmp);
}

void input()
{
    scanf("%d%d", &n, &m);
    memset(dis, -1, sizeof(dis));
    int u, v, w;
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &u, &v, &w);
        dis[u][v] = dis[v][u] = myMin(dis[u][v], w);
    }
}

void spfa()
{
    pii k;
    int now, state, pre;
    queue<pii> q;
    q.push(pii(1, 0));
    vis[1][0] = true;
    while (!q.empty())
    {
        k = q.front();
        q.pop();
        now = k.first; state = k.second;
        vis[now][state] = false;
        for (int i = 1; i <= n; ++i)
        {
            if (i == now || dis[i][now] == -1)
                continue;
            pre = p[i][state|(1<<now)];
            p[i][state|(1<<now)] = myMin(p[i][state|(1<<now)], p[now][state]+dis[i][now]);
            if (pre != p[i][state|(1<<now)] && !vis[i][state|(1<<now)])
            {
                vis[i][state|(1<<now)] = true;
                q.push(pii(i, state|(1<<now)));
            }
        }
    }
}

void work()
{
    if (n == 1)
    {
        printf("0
");
        return;
    }
    memset(p, -1, sizeof(p));
    memset(vis, false, sizeof(vis));
    p[1][0] = 0;
    int state = 0;
    for (int i = 1; i <= n; ++i)
        state |= (1<<i);
    spfa();
    printf("%d
", p[1][state]);
}

int main()
{
    //freopen("test.in", "r", stdin);
    int T;
    scanf("%d", &T);
    for (int times = 0; times < T; ++times)
    {
        input();
        work();
    }
    return 0;
}

View Code

ACM学习历程—HDU5418 Victor and World(动态规划 && 状压)

相关推荐