稀疏图的多源最短路径问题，用heap+disjktra解决。
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
using namespace std;
ifstream fin("butter.in");
ofstream fout("butter.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
int n,p,c;
struct edge{
int node;
int weight;
edge(int n,int w):node(n),weight(w){
}
};
struct graph_node{
list<edge> adj;
};
struct pri_que_node{
int num;
int dist;
pri_que_node(int n,int d):num(n),dist(d){
};
bool operator< (const pri_que_node &n2) const{
return dist>n2.dist;
}
};
graph_node graph[801];
int cow_place[801];
int shortest_path[801][801];
void get_shortest(int n)
{
for(int i=1;i<801;++i)
shortest_path[n][i] = INT_MAX;
shortest_path[n][n] = 0;
priority_queue<pri_que_node> pq;
for(list<edge>::iterator li = graph[n].adj.begin();
li!=graph[n].adj.end();
li++){
pq.push( pri_que_node(li->node,li->weight) );
shortest_path[n][li->node] = li->weight;
}
while( !pq.empty() ){
pri_que_node node = pq.top();
pq.pop();
if( node.dist> shortest_path[n][node.num] )
continue;
shortest_path[n][node.num] = node.dist;
for(list<edge>::iterator li = graph[node.num].adj.begin();
li!=graph[node.num].adj.end();
li++){
if( node.dist+li->weight < shortest_path[n][li->node] ){
shortest_path[n][li->node] = node.dist+li->weight;
pq.push( pri_que_node(li->node, shortest_path[n][li->node]) );
}
}
}
}
void solve()
{
in>>n>>p>>c;
for(int i=0;i<n;++i)
in>>cow_place[i];
int a,b,w;
while(c--){
in>>a>>b>>w;
graph[a].adj.push_back( edge(b,w) );
graph[b].adj.push_back( edge(a,w) );
}
#ifdef _DEBUG
for(int i=1;i<=p;++i){
if(!graph[i].adj.empty()){
cout<<"node:"<<i<<" ";
for(list<edge>::iterator li = graph[i].adj.begin();
li!=graph[i].adj.end();
li++){
cout<<"("<<li->node<<","<<li->weight<<")";
}
cout<<endl;
}
}
#endif
for(int i=1;i<=p;++i)
get_shortest(i);
int res = INT_MAX;
for(int i=1;i<=p;++i){
int t = 0;
for(int j=0;j<n;++j){
t+= shortest_path[i][cow_place[j]];
}
res = min(res,t);
}
out<<res<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}