题目：https://ac.nowcoder.com/acm/contest/7818/B
经典TSP问题，推荐看这篇文章：https://www.cnblogs.com/smashfun/p/11432110.html
模版：
for (int i = 1; i <= n; i++) dp[1<<(i - 1)][i] = 0; int ans = inf; for (int i = 0; i < (1<<n); i++) //状态的个数，从n个0到n个1 for (int j = 1; j <= n; j++) { if (i&(1<<(j - 1))) //必须是访问过的点j才可以，访问过的才知道最优子结构 { for (int k = 1; k <= n; k++) if (i&(1<<(k - 1)) != 0 && g[k][j] != -1) //必须是访问过的k点且边存在 dp[i][j] = min(dp[i^(1<<(j - 1))][k] + g[k][j], dp[i][j]); } if (i == (1<<n) - 1) ans = min(ans, dp[i][j]); } if (ans == inf) return -1; return ans;
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; //typedef __int128_t LL; typedef double db; #define rep(a,b,c) for(ll a=b;a<=c;a++) #define per(a,b,c) for(ll a=b;a>=c;a--) #define go(a,b) for(ll a=head[b];a;a=e[a].to) #define endl ' ' #define V vector #define pb push_back #define mp make_pair #define mem(a,b) memset(a,b,sizeof(a)) const ll amn=1e5+5,mod=1e9+7,inf=0x3f3f3f3f; ll head[amn],etot; struct eg{ ll to,v; db w; eg(){} eg(ll to,ll v,db w):to(to),v(v),w(w){} }e[amn]; void einit(){ etot=0; mem(head,0); } void add(ll u,ll v,db w){ e[++etot]=eg(head[u],v,w); head[u]=etot; } void sovle(); int main(){ ios::sync_with_stdio(0); ll T=1; //cin>>T; while(T--){ sovle(); } } ll n,m,k; ll s,t; struct Node{ int id; db d; Node() {} Node(int id, db d):id(id),d(d){} bool operator < (const Node &A) const { return d > A.d; } }; ll vis[amn]; db dis[amn]; void dij(int st){ for(int i=1; i<=n; i++){ vis[i] = 0; dis[i] = inf; } dis[st] = 0; priority_queue <Node> Q; while(Q.size())Q.pop(); Q.push(Node(st, 0)); Node nd; while(!Q.empty()){ nd = Q.top(); Q.pop(); if(vis[nd.id]) continue; vis[nd.id] = true; go(i,nd.id){ int j = e[i].v; db k = e[i].w; if(nd.d + k < dis[j] && !vis[j]){ dis[j] = nd.d + k; Q.push(Node(j, dis[j])); } } } } ll kl[55][5]; ll d[55][55]; ll dp[1<<20][25]; void sovle(){ ll ans=inf; mem(head,0); mem(d,0x3f); cin>>n>>m>>k; rep(i,1,m){ ll u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } rep(i,1,k){ rep(j,0,1){ cin>>kl[i][j]; } } rep(i,1,k){ dij(kl[i][0]); rep(j,1,k){ d[i][j]=dis[kl[j][1]]; } } mem(dp,0x3f); rep(i,0,k-1){ dp[1<<(i)][i+1]=d[i+1][i+1]; } rep(i,0,(1<<k)-1){ rep(j,0,k-1){ if(i&(1<<(j))){ rep(v,0,k-1){ if((i&(1<<(v)))!=0&&d[j+1][v+1]!=inf){ dp[i][j+1]=min(dp[i][j+1],dp[i^(1<<(j))][v+1]+d[j+1][v+1]+d[j+1][j+1]); } } if(i==(1<<(k))-1){ ans=min(ans,dp[i][j+1]); } } } } if(ans==inf)ans=-1; cout<<ans<<endl; } /* 5 5 3 1 2 1 2 3 2 3 4 3 4 5 4 5 2 4 2 3 1 2 5 3 */