1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 #include<cstring> 5 #define INF 1<<30 6 #define Min(x,y) x>y?y:x 7 using namespace std; 8 int dist[1003],vis[1003]; 9 int map[1003][1003],city[105]; 10 int N,M,P,Q; 11 int Dijkstra() 12 { 13 int i,j,mark,mindis,min_d; 14 memset(vis,0,sizeof(vis)); 15 for(i=1; i<=M; i++)dist[i] = INF;//初始化 16 dist[Q] = 0; //以目的地作为起点 17 for(i=1; i<=M; i++){ 18 mark = -1; 19 mindis = INF; 20 for(j=1; j<=M; j++) 21 if( !vis[j] && dist[j] < mindis){ 22 mindis = dist[j]; 23 mark = j; 24 } 25 vis[mark] = 1; 26 for(j=1; j<=M; j++)if( !vis[j] && map[mark][j]) 27 dist[j] = Min(dist[j],dist[mark] + map[mark][j]); 28 } 29 min_d = dist[city[1]]; 30 for(i=1; i<=N; i++) 31 if(dist[city[i]] < min_d)min_d = dist[city[i]]; 32 return min_d; 33 } 34 int main() 35 { 36 //freopen("in.txt","r",stdin); 37 int T,i,vi,vj,w; 38 cin>>T; 39 while(T--) 40 { 41 cin>>N>>M>>P>>Q; 42 memset(map,0,sizeof(map)); 43 for(i=1; i<=N; i++)cin>>city[i]; 44 for(i=1; i<=P; i++){ 45 cin>>vi>>vj>>w; 46 if(map[vi][vj]) 47 map[vi][vj] = map[vi][vj]<w?map[vi][vj]:w; 48 else 49 map[vi][vj] = map[vj][vi] = w; 50 } 51 cout<<Dijkstra()<<endl; 52 } 53 return 0; 54 } 55