SPFA70分,WA了三个点,求助!
查看原帖
SPFA70分,WA了三个点,求助!
388391
我是小何子啊楼主2020/12/9 13:43

不知道哪里错了,样例点2,9,10WA了,求大佬看看我哪错了。

#include<cstdio>
using namespace std;
long long mi=0x7fffffff,ans,dis[1001];
int n,p,d,o[1001],a,b,c,tot,u[1001],ti[1001],head[1001],next[100001],to[100001],len[100001];
int add(int x,int y,int z){
	next[tot]=head[x];
	to[tot]=y;
	len[tot]=z;
	head[x]=tot++;
}
void spfa(int x){
	int h=0,t=0,k;
	ti[++t]=x;
	u[x]=1;
	dis[x]=0;
	while(h<t){
		k=ti[++h];
		u[k]=0;
		for(int i=head[k];i;i=next[i]){
			if(dis[to[i]]>dis[k]+len[i]){
				dis[to[i]]=dis[k]+len[i];
				if(!u[to[i]]){
					u[to[i]]=1;
					ti[++t]=to[i];
				}
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&p,&d);
	for(int i=1;i<=n;++i) scanf("%d",&o[i]);
	for(int i=1;i<=d;++i){
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	for(int i=1;i<=p;++i){
		ans=0;
		for(int j=1;j<=p;++j) u[j]=0,dis[j]=0x7fffffff;
		spfa(i);
		for(int j=1;j<=n;++j) ans+=dis[o[j]];
		if(mi>ans) mi=ans;
	}
	printf("%d",mi);
	return 0; 
}
2020/12/9 13:43
加载中...