题目描述
给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
样例
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
18
算法1
状压dp板子题 $O(n^2*2^n)$
状压dp。
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
// #include <iostream>
// #include <cstdio>
// #include <cstring>
// #include <vector>
// #include <algorithm>
// #include <queue>
using namespace std;
typedef long long int ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repn(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=a;i>=n;i--)
#define mem(a,b) memset(a,b,sizeof(a))
typedef unsigned long long int ull;
#define pb push_back
//#define mp make_pair
ll gcd(ll a,ll b){if(b==0)return a;else return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int mod=1e9+7;
const double pi=acos(-1);
ll ksm(ll a,ll b)
{
ll rec=1;
while(b)
{
if(b%2)
{
rec*=a;
rec%=mod;
}
ll tmp=a%mod;
a*=a;
b>>=1;
rec%=mod;
}
rec%=mod;
return rec;
}
int G[25][25];
ll f[1<<20][25];
const ll inf=0x3f3f3f3f3f3f3f3f;
int main()
{
int n;
cin>>n;
rep(i,0,n)
{
rep(j,0,n)
cin>>G[i][j];
}
mem(f,inf);
f[1][0]=0;
repn(i,1,1<<n)
{
rep(j,0,n)
{
if((i>>j&1)==1)//第j个节点被访问过
{
rep(k,0,n)
{
if(((i^1<<j)>>k)&1==1)//节点j没被访问过的情况下k节点被访问过
{
f[i][j]=min(f[i][j],f[(i^1<<j)][k]+G[k][j]);
}
}
}
}
}
cout<<f[(1<<n)-1][n-1]<<endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
您算法2搁着是准备拿图灵奖吗?
这不是给的模板么,测试下题解功能。