洛谷看到的剪枝,感觉很强
acw题解居然没人写这个floyd的,floyd短太多了
而且这个剪枝并不复杂
const int N = 890;
int a[N][N];
#define eps(i,a,b) for(int i=a;i<=b;i++)
ll n,m,c;
int p[N];
void floyd()
{
//因为是双向边,我们只要更新一半就行了
for(int k=1;k<=n;k++)//floyd三重循环
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if(a[i][j]>a[i][k]+a[k][j])
{
a[i][j]=a[i][k]+a[k][j];
a[j][i]=a[i][j];
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie();cout.tie();
cin>>m>>n>>c;
eps(i,1,n)
eps(j,1,n){
if(i==j)a[i][j]=a[j][i]=0;
else a[i][j]=a[j][i]=0x3f3f3f3f;
}
eps(i,1,m){
int x;cin>>x;p[x]++;
}
while(c--){
int i,j,z;
cin>>i>>j>>z;
a[i][j]=a[j][i]=min(a[i][j],z);
}
floyd();
ll res=1e15;
eps(i,1,n)
{
ll ans=0;
eps(j,1,n){
ans+=a[i][j]*p[j];
}
res=min(ans,res);
}
cout<<res;
return 0;
}