已死的SPFA
题意很简单,让你找一个牧场,使得每只奶牛到这个牧场的距离和最小
解题思路
暴力枚举每个牧场即可
参考代码
#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define INF 0x3f3f3f3f
int n,m;
int s,t,d,qqs,zzd,p,minn=INF;
int nn[N*N];
int w[N*N];
int dis[N*N];
bool vis[N*N];
struct spfa {
int qd,jl;
spfa(int x,int y) : qd(x),jl(y) {}
};
vector<spfa> boy[N];
queue<int> lunai;
void SPFA (int s) {
memset(vis,0,sizeof(vis));
for(int i=1; i<=m; i++)
dis[i]=INF;
dis[s]=0;
lunai.push(s);
while(lunai.size()) {
int x=lunai.front();
lunai.pop();
vis[x]=0;
for(int i=0; i<boy[x].size(); i++) {
int l=boy[x][i].qd,w=boy[x][i].jl;
if(dis[l]>dis[x]+w) {
dis[l]=dis[x]+w;
if(!vis[l]) {
vis[l]=1;
lunai.push(l);
}
}
}
}
}
int main() {
scanf("%d%d%d",&n,&m,&p);
for(int i=1; i<=n; i++)
scanf("%d",&nn[i]);
for(int i=1; i<=p; i++) {
scanf("%d%d%d",&s,&t,&d);
boy[s].push_back(spfa(t,d));
boy[t].push_back(spfa(s,d));
}
for(int i=1; i<=m; i++) {
SPFA(i);
int ans=0;
for(int j=1; j<=n; j++) {
ans+=dis[nn[j]];
if(ans>minn)
break;
}
if(ans<minn)
minn=ans;
}
printf("%d",minn);
}
可爱QAQ