香甜的黄油

spfa已死？

#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3f3f3f3f 
#define pii pair<int,int>
const int N=805;
const int M=1455;
int id[605];
struct edge{
    
	int to,nxt,w;
}e[M<<1];
int head[N];
int cnt;
void add(int u,int v,int w){
    
	e[++cnt].w=w;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int dist[N];
bool vis[N];
int n,p,m;//奶牛，农场，路 
int spfa(int s){
    
	for(int i=1;i<=p;i++){
    
		dist[i]=inf;
		vis[i]=false;
	}
	queue<int> Q;
	Q.push(s);
	dist[s]=0;
	vis[s]=true;
	while(!Q.empty()){
    
		int t=Q.front();
		Q.pop();vis[t]=false;
		for(int i=head[t];i;i=e[i].nxt){
    
			int to=e[i].to;
			int w=e[i].w;
			if(dist[to]>dist[t]+w){
    
				dist[to]=dist[t]+w;
				Q.push(to);
			}
		}
	}
	int res=0;
	for(int i=0;i<n;i++){
    
		if(dist[id[i]]==inf)return inf;
		res+=dist[id[i]];
	}
	return res;
}
int dijikstra(int s){
    
	for(int i=1;i<=p;i++){
    
		dist[i]=inf;
		vis[i]=false;
	}
	priority_queue<pii, vector<pii> ,greater<pii> > Q;
	Q.push({
    0,s});
	dist[s]=0;
	for(int k=0;k<p;k++){
    
		if(Q.empty())break;
		pii t=Q.top(); Q.pop();
		int v=t.second;
		if(vis[v]){
    
			k--;
			continue;
		}
		vis[v]=1;
		for(int i=head[v];i;i=e[i].nxt){
    
			int to=e[i].to;
			int w=e[i].w;
			if(dist[to]>dist[v]+w){
    
				dist[to]=dist[v]+w;
				Q.push({
    dist[to],to});
			}
		}
	}
	int res=0;
	for(int i=0;i<n;i++){
    
		if(dist[id[i]]==inf)return inf;
		res+=dist[id[i]];
	}
// cout<<res<<endl;
	return res;
} 

int main(int argc, char** argv) {
    
// int n,p,m;//奶牛，农场，路 
	cin>>n>>p>>m;
	for(int i=0;i<n;i++)cin>>id[i];
	int u,v,w;
	while(m--){
    
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	} 
	int res=inf; 

	for(int i=1;i<=p;i++)res=min(res,dijikstra(i));//所有奶牛到i的距离之和 
	cout<<res;
	return 0;
}

稍稍改动id[x]到count[x]
通过下面这个样例发现的，没错，就是多了一个无法到达的牧场而已

3 5 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

#include <iostream>
#include <queue>
using namespace std;
#define inf 0x3f3f3f3f 
#define pii pair<int,int>
const int N=805;
const int M=1455;
int count[N];
int id[605];
struct edge{
    
	int to,nxt,w;
}e[M<<1];
int head[N];
int cnt;
void add(int u,int v,int w){
    
	e[++cnt].w=w;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int dist[N];
bool vis[N];
int n,p,m;//奶牛，农场，路 
//int spfa(int i){
    
// 
// return 0;
//}
int dijikstra(int s){
    
	for(int i=1;i<=p;i++){
    
		dist[i]=inf;
		vis[i]=false;
	}
	priority_queue<pii, vector<pii> ,greater<pii> > Q;
	Q.push({
    0,s});
	dist[s]=0;
	for(int k=0;k<p;k++){
    
		if(Q.empty())break;
		pii t=Q.top(); Q.pop();
		int v=t.second;
		if(vis[v]){
    
			k--;
			continue;
		}
		vis[v]=true;
		for(int i=head[v];i;i=e[i].nxt){
    
			int to=e[i].to;
			int w=e[i].w;
			if(dist[to]>dist[v]+w){
    
				dist[to]=dist[v]+w;
				Q.push({
    dist[to],to});
			}
		}
	}
	int res=0;
// for(int i=0;i<n;i++){
    
// if(dist[id[i]]==inf)return inf;
// res+=dist[id[i]];
// }
// cout<<p<<endl;
// for(int i=1;i<=p;i++)cout<<dist[i]<<" "<<count[i]<<endl;
// cout<<"hhhhh"<<endl;
	for(int i=1;i<=p;i++){
    
		if(dist[i]==inf&&count[i])return inf;//害！！！万一这个点没有牛呢，不能直接返回inf
		res+=dist[i]*count[i];
	}
// cout<<res<<endl;
	return res;
} 

int main(int argc, char** argv) {
    
// int n,p,m;//奶牛，农场，路 
	cin>>n>>p>>m;
	int x;
	for(int i=0;i<n;i++){
    
		cin>>x;
		count[x]++;
	}
	int u,v,w;
	while(m--){
    
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	} 
	int res=inf; 
	
	for(int i=1;i<=p;i++)res=min(res,dijikstra(i));//所有奶牛到i的距离之和 
	cout<<res;
	return 0;
}