题解 | #郊区春游#

弗洛伊德与哈密顿结合；**最小路径与状态压缩（动态规划）
代码如下：
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
const int N=201;
int road[N][N];
int p[N];
int dp[1<<15][N];
int n,m,r;

void floyd()
{
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      for(int k=1;k<=n;k++)
      road[i][j]=min(road[i][j],road[i][k]+road[k][j]);
}
int main()
{
   cin>>n>>m>>r;
   for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     if(i==j) road[i][j]=0;
     else
     road[i][j]=0x3f3f3f3f;
   while(m--)
   { 
      int a,b,c;
      cin>>a>>b>>c;
      road[a][b]=road[b][a]=c;
   }
   floyd();
   for(int i=0;i<r;i++)
   cin>>p[i];
   memset(dp,0x3f,sizeof(dp));
   for(int j=0;j<r;j++)
   dp[1<<j][j]=0;
   for(int i=0;i<1<<r;i++)
     for(int j=0;j<r;j++)
     if(i>>j&1)
     {
        for(int k=0;k<r;k++)
        if((i-(1<<j))>>k&1)
        dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+road[p[k]][p[j]];
     }
     int res=0x3f3f3f3f;
     for(int i=0;i<r;i++)
     ans=min(ans,dp[(1<<r)-1][i]);
     cout<<ans<<endl;
   return 0;
}