NC16122. 郊区春游
描述
输入描述
第一行三个整数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
C++11(clang++ 3.9) 解法, 执行用时: 33ms, 内存消耗: 4836K, 提交时间: 2020-02-28 21:55:59
#include<bits/stdc++.h>
using namespace std;
int i,j,k,s,n,m,R,T[205][205],Q[20],D[1<<16][16];
int main()
{
scanf("%d%d%d",&n,&m,&R);
for(i=0;i<R;i++)
scanf("%d",&Q[i]);
memset(T,0x3f3f3f3f,sizeof(T)),memset(D,0x3f3f3f3f,sizeof(D));
for(i=1;i<=n;i++)
T[i][i]=0;
while(m--)
scanf("%d%d%d",&i,&j,&k),T[i][j]=min(T[i][j],k),T[j][i]=T[i][j];
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;
for(i=0;i<R;i++)
D[1<<i][i]=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[k]][Q[j]]);
}
for(m=1e9,i=0;i<R;i++)
m=min(m,D[s][i]);
printf("%d\n",m);
return 0;
}