题目链接
https://cn.vjudge.net/problem/HDU-5418
题意:有n个城市，在n个城市之间有m条带权双向边，若从1号城市去经过其它全部的2到n号城市并且最后回到1号城市的最短路径。
分析
这道题与最长哈密顿回路不同的地方在于它没有每个点只能经过一次的限制,这样的话状态转移似乎比较麻烦而且很难保证没有后效性.
既然这样我们有没有方法将它转化成一个更好处理的模型呢.我们先用Floyd跑出两两之间的最短路,然后再跑一遍最长哈密顿路径
这时候就有个naive的问题,这个Floyd处理后的路径难道不会包含其他点吗,这样难道不会存在错误的状态转移吗?我一开始也想了好久.
这时候JYH大佬就跳了出来,解释道虽然会不合法地扩展,但是我们也会枚举到合法扩展的状态,显然合法扩展的状态比不合法扩展的状态不知道高到哪去了,于是当然资瓷Floyd处理了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <queue>
#include <bitset>
#define ll long long
#define ri register int
using std::min;
using std::max;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=19;
const int inf = 0x7fffffff;
int g[maxn][maxn];
int f[1<<18][maxn];
int n,m;
inline void clear(){
memset(g,0x3f,sizeof(g));
memset(f,0x3f,sizeof(f));
for(ri i=0;i<n;i++)g[i][i]=0;
f[1][0]=0;
}
inline void Floyd(){
for(ri k=0;k<n;k++){
for(ri i=0;i<n;i++){
for(ri j=0;j<n;j++){
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
return ;
}
int main(){
int T,sz;
int x,y,z,ans=0;
read(T);
while(T--){
read(n),read(m);
clear();
sz=1<<n;
for(ri i=1;i<=m;i++){
read(x),read(y),read(z);
x--,y--;
g[x][y]=g[y][x]=min(g[x][y],z);
}
Floyd();
for(ri p=1;p<sz;p+=1){
for(ri i=0;i<n;i++) if((p>>i)&1){
for(ri j=0;j<n;j++) if((p>>j)&1){
f[p][i]=min(f[p][i],f[p^(1<<i)][j]+g[j][i]);
}
}
}
ans=inf;
for(ri i=0;i<n;i++)ans=min(ans,f[sz-1][i]+g[i][0]);
printf("%d\n",ans);
}
return 0;
}
|