本题是多源最短路问题 但使用弗洛伊德算法会超时 而因为边数目比较少 所以用队列优化后的迪杰斯特拉算法可以通过
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
<<;
struct Edge{
int from,to,dist;
};
struct Node{
int u,d;
bool operator<(const Node& n)const{
return d>n.d;
}
};
vector<Edge> edges;
+],cnt[+],v[+];
int N,M,C;
vector<+];
void DJSTL(int s){
;i<=N;i++) d[i]=inf,v[i]=;
d[s]=;
priority_queue<Node> Q;
Q.push((Node){s,});
while(!Q.empty()){
Node x=Q.top();Q.pop();
int u=x.u;
v[u]=;
;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(v[e.to]) continue;
if(d[u]+e.dist<d[e.to]){
d[e.to]=d[u]+e.dist;
Q.push((Node){e.to,d[e.to]});
}
}
}
}
int main()
{
memset(cnt,,sizeof(cnt));
int cow,from,to,dist;
cin>>C>>N>>M;
while(C--){
cin>>cow;
cnt[cow]++;
}
while(M--){
cin>>from>>to>>dist;
edges.push_back((Edge){from,to,dist});
edges.push_back((Edge){to,from,dist});
int m=edges.size();
G[);
G[to].push_back(m-);
}
int ans=inf;
;i<=N;i++){
;
DJSTL(i);
;i<=N;i++) tans+=d[i]*cnt[i];
ans=min(ans,tans);
}
cout<<ans;
;
}