稀疏圖的多源最短路徑問(wèn)題，用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;
}