DP60 郊区春游

首先使用floyd,求出各个点之间的最短距离，然后使用状压dp;

dp[i][j]:i表示已经访问过的城市的状态(包括j)（题中需要访问R个城市，这里就有（1<<R）-1个状态），j表示当前在第j个城市.

描述

今天春天铁子的班上组织了一场春游，在铁子的城市里有n个郊区和m条无向道路，第i条道路连接郊区Ai和Bi，路费是Ci。经过铁子和顺溜的提议，他们决定去其中的R个郊区玩耍（不考虑玩耍的顺序），但是由于他们的班费紧张，所以需要找到一条旅游路线使得他们的花费最少，假设他们制定的旅游路线为V1, V2 ,V3 ... VR，那么他们的总花费为从V1到V2的花费加上V2到V3的花费依次类推，注意从铁子班上到V1的花费和从VR到铁子班上的花费是不需要考虑的，因为这两段花费由学校报销而且我们也不打算告诉你铁子学校的位置。

输入描述：

第一行三个整数n, m, R(2 ≤ n ≤ 200, 1 ≤ m ≤ 5000, 2 ≤ R ≤ min(n, 15))。
第二行R个整数表示需要去玩耍的郊区编号。
以下m行每行Ai, Bi, Ci(1 ≤ Ai, Bi ≤ n, Ai ≠ Bi, Ci ≤ 10000)
保证不存在重边。

输出描述：

输出一行表示最小的花费

示例1

输入：

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

复制输出：

3

#include <iostream>
#include<string.h>
using namespace std;
#define inf 0x3f3f3f3f
int R[20];
int dis[205][205];
int dp[1<<16][20];
int main() {
    int n,m,r;
    scanf("%d%d%d",&n,&m,&r);
    memset(dis,inf,sizeof(dis));
    memset(dp,inf,sizeof(dp));
    for(int i=0;i<r;i++)
    {
        scanf("%d",&R[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        dis[x][y]=w;
        dis[y][x]=w;
    }
    //得到任意两点的最短距离
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    for(int i=0;i<r;i++)
    {
        dp[1<<i][i]=0;//初始化，当前在第i个城市，没有访问其他城市
    }
    int len=(1<<r)-1; //状态
    for(int k=1;k<len;k++)//对每个状态进行枚举
    {
        for(int i=0;i<r;i++)//枚举已经访问的状态
        {
           if(((1<<i)&k)==0) //判断是否访问过i,如果没有就跳过
            {
                continue;
            }
            for(int j=0;j<r;j++)//枚举将要访问的状态
            {
                int t=1<<j;
                if((t&k)!=0)//判断是否访问过j如果访问了,就跳过。
                {
                    continue;
                }
                dp[k+t][j]=min(dp[k+t][j],dp[k][i]+dis[R[i]][R[j]]);
            }
        }
    }
    int ans=1e9;
    for(int i=0;i<r;i++)
    {
        ans=min(ans,dp[len][i]);
    }
    printf("%d\n",ans);
    return 0;
}