1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 using namespace std; 6 #define maxn 0x7fffffff; 7 int map[1000][1000]; 8 int a[1000][1000]; 9 int dis[1000]; 10 int n,mc,m; 11 int shu[1000]; 12 int sum[1000]; 13 int vis[1000]; 14 queue<int>qq; 15 int minn=maxn; 16 int sumnow; 17 void spfa(int x) 18 { 19 while(qq.size()!=0)qq.pop(); 20 memset(dis,0x7f,sizeof(dis)); 21 //memset(vis,0x7f,sizeof(vis)); 22 vis[x]=1; 23 dis[x]=0; 24 qq.push(x); 25 while(qq.size()!=0) 26 { 27 int w=qq.front(); 28 for(int i=1;i<=sum[w];i++) 29 { 30 if(dis[a[w][i]]>dis[w]+map[w][a[w][i]]) 31 { 32 dis[a[w][i]]=dis[w]+map[w][a[w][i]]; 33 if(vis[a[w][i]]==0) 34 { 35 qq.push(a[w][i]); 36 vis[a[w][i]]=1; 37 } 38 } 39 } 40 qq.pop(); 41 vis[w]=0; 42 } 43 sumnow=0; 44 for(int i=1;i<=mc;i++) 45 { 46 sumnow=sumnow+dis[i]*shu[i]; 47 } 48 if(sumnow<minn) 49 { 50 minn=sumnow; 51 } 52 } 53 int main() 54 { 55 memset(map,0x7f,sizeof(map)); 56 cin>>n>>mc>>m; 57 for(int i=1;i<=n;i++) 58 { 59 int hao; 60 cin>>hao; 61 shu[hao]++; 62 } 63 for(int i=1;i<=m;i++) 64 { 65 int q,z,l; 66 cin>>q>>z>>l; 67 map[q][z]=map[z][q]=l; 68 a[q][++sum[q]]=z; 69 a[z][++sum[z]]=q; 70 } 71 for(int i=1;i<=mc;i++) 72 { 73 spfa(i); 74 } 75 printf("%d",minn); 76 return 0; 77 }