题意
一个联通图里给定若干个点，求他们到某点距离之和的最小值。
题解
枚举到的某点，然后优先队列优化的dijkstra求最短路，把给定的点到其的最短路加起来，更新最小值。复杂度是
。 注意此题给的n是奶牛个数，p是牧场个数，p才是点的个数N，所以head、dis、vis要开到1000。
代码
代码语言：javascript复制/*
USER:19flipp1
TASK:butter
LANG:C
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define in(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout);
#define ll long long
#define N 1005
#define M 3000
#define inf 0x3f3f3f3f
using namespace std;
int n,p,c,pos[N];
struct edge{
int to,next,w;
}e[M];
int head[N],cnt;
void add(int u,int v,int w){
e[cnt]=edge{v,head[u],w};
head[u]=cnt ;
}
struct qnode{
int v,c;
int operator<(const qnode& r)const{
return c>r.c;
}
};
int d[N],vis[N];
int dijkstra(int s){
for(int i=1;i<=p;i ){d[i]=inf;vis[i]=0;}
priority_queue<qnode>que;
while(!que.empty())que.pop();
d[s]=0;
que.push((qnode){s,0});
while(!que.empty()){
int u=que.top().v;
que.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(!vis[v]&&d[v]>d[u] w){
d[v]=d[u] w;
que.push((qnode){v,d[v]});
}
}
}
int ans=0;
for(int i=1;i<=n;i )ans =d[pos[i]];
return ans;
}
int main(){
in(butter);
memset(head,-1,sizeof head);
scanf("%d%d%d",&n,&p,&c);
for(int i=1;i<=n;i )scanf("%d",&pos[i]);
for(int i=1;i<=c;i ){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
int ans=inf;
for(int i=1;i<=p;i ){
int tans=dijkstra(i);
ans=min(ans,tans);
}
printf("%dn",ans);
return 0;
}
/*
P2
P1 @--1--@ C1
|
|
5 7 3
|
| C3
C2 @--5--@
P3 P4
*/
