floyed first 设f[i][S]表示取到了S集合中的所有点（不一定是经过的所有点），最后停在了i的最优值。
初始就f[i][{i}] = dis[1][i]
状态转移直接转就好了
f[i][S] + dis[i][j] -> f[j][S + {j}]其中 i 属于 S,1 <= j <= n
设tim[S] = min{f[i][S]}
答案就取到
ans = min{max{tim[S],tim[Cs]}}
#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
inline void read(int &x){
x=;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=*x+ch-'',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_abs(const int &x){return x < ? -x : x;}
const int maxn = ;
const int maxs = (<<) + ;
int dis[maxn][maxn],n,f[maxn][maxs],tim[maxs];
inline void init(){
memset(dis,0x3f,sizeof dis);
memset(f,0x3f,sizeof f);
memset(tim,0x3f,sizeof tim);
}
void floyed(){
for(int i=;i<=n;++i){
dis[i][i] = ;
for(int j=;j<=n;++j){
if(i == j) continue;
for(int k=;k<=n;++k){
dis[i][j] = cat_min(dis[i][j],
dis[i][k] + dis[k][j]);
}
}
}return;
}
map<int,int>ma;
int main(){ int m;read(n);read(m);
init();
for(int i=,u,v,d;i<=m;++i){
read(u);read(v);read(d);
if(dis[u][v] > d) dis[u][v] = dis[v][u] = d;
}
floyed();
for(int i=;i<=;++i) ma[<<i] = i+;
for(int i=;i<=n;++i) f[i][(<<) | (<<(i-))] = dis[][i];
for(int i=,x=;i<(<<n);x = (++i) ){
while(x){
int p = ma[x&-x];x -=x&-x;
for(int j=;j<=n;++j){
if( f[j][i | (<<(j-))] > f[p][i] + dis[p][j]){
f[j][i | (<<(j-))] = f[p][i] + dis[p][j];
}
}
}
}
for(int i=,x=;i<(<<n);x = (++i) ){
while(x){
int p = ma[x & -x];x -= x&-x;
tim[i]=cat_min(tim[i],f[p][i]);
}
}
int ans = 0x7f7f7f7f;
for(int i=;i<(<<n);++i){
ans = cat_min(ans,cat_max(tim[i],
tim[ | (( ( << n)- )^i) ]));
}printf("%d\n",ans);
//getchar();getchar();
fclose(stdin);fclose(stdout);
return ;
}