状压dp

链接：https://ac.nowcoder.com/acm/problem/16122

郊区春游
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
今天春天铁子的班上组织了一场春游，在铁子的城市里有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<bits/stdc++.h>
using namespace std;
//const int N=1010;
int i,j,k,s,n,m,R,T[205][205],Q[20],D[1<<16][16];
int main()
{
    cin>>n>>m>>R;
    for(int i=0;i<R;i++)cin>>Q[i];
    memset(T,0x3f3f3f3f,sizeof(T)),memset(D,0x3f3f3f3f,sizeof(D));
    for(i=1;i<=n;i++)T[i][i]=0;
    while(m--){
        cin>>i>>j>>k;
        T[i][j]=min(T[i][j],k),T[j][i]=T[i][j];
    }
    //floyd最短路
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(T[i][k]+T[k][j]<T[i][j])T[i][j]=T[i][k]+T[k][j];
    s=(1<<R)-1;//所有要去的城市15个
    for(i=0;i<R;i++)D[1<<i][i]=0;//自己和自己的距离都为0
    for(i=0;i<=s;i++)
        for(j=0;j<R;j++){//枚举结束的点
        if((i&(1<<j))==0)continue;
        for(k=0;k<R;k++)
            D[i^(1<<k)][k]=min(D[i^(1<<k)][k],D[i][j]+T[Q[j]][Q[k]]);//找出最短路
    }
    for(m=1e9,i=0;i<R;i++){
        m=min(m,D[s][i]);
    }
    cout<<m<<endl;
}