HDU 5418 / Victor and World

Posted on By 二价氢

题目:HDU 5418

TSP问题

可使用状态压缩的动态规划,状态压缩的最短路,等等的算法解决,注意原来读入的边数量太多,要先去除重边。

AC-Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 16 + 1;
typedef pair<int , int> pii;
int len[maxn][maxn];
int d[maxn][1 << maxn];
bool inq[maxn][1 << maxn];
vector<pii> e[maxn];
int n , m;
void work()
{
    memset(len , 0x7f , sizeof(len));
    memset(d , 0x3f , sizeof(d));
    memset(inq , 0 , sizeof(inq));
    scanf("%d%d" , &n , &m);
    int tu , tv , tc;
    for (int i = 1 ; i <= n ; i++) e[i].clear();
    for (int i = 0 ; i < m ; i++)
    {
        scanf("%d%d%d" , &tu , &tv , &tc);
        len[tv][tu] = len[tu][tv] = min(len[tu][tv] , tc);
    }
    for (int i = 1 ; i <= n ; i++)
        for (int j = i + 1 ; j <= n ; j++)
            if (len[i][j] < 0x7f7f7f7f)
            {
                e[i].push_back(pii(j , len[i][j]));
                e[j].push_back(pii(i , len[i][j]));
            }
    queue<pii> q;
    q.push(pii(1 , 1));
    d[1][1] = 0;
    while (!q.empty())
    {
        pii tq = q.front();
        q.pop();
        inq[tq.first][tq.second] = false;
        int td = d[tq.first][tq.second];
        for (vector<pii>::iterator i = e[tq.first].begin() ; i != e[tq.first].end() ; i++)
        {
            if (d[i->first][tq.second | (1 << (i->first - 1))] > (td + i -> second))
            {
                d[i->first][tq.second | (1 << (i->first - 1))] = (td + i -> second);
                if (!inq[i->first][tq.second | (1 << (i->first - 1))])
                {
                    q.push(pii(i->first , tq.second | (1 << (i->first - 1))));
                    inq[i->first][tq.second | (1 << (i->first - 1))] = true;
                }
            }
        }
    }
    printf("%d\n" , d[1][(1 << n) - 1]);
}
int main()
{
    int t;
    scanf("%d" , &t);
    while (t--)
        work();
    return 0;
}