为什么这个dis初值不能是无穷大???(已过)
查看原帖
为什么这个dis初值不能是无穷大???(已过)
939191
w_camellia楼主2023/7/11 11:08

如标题 如果我用的是无穷大就会wa掉最后一个点 非常迷惑 (用的spfa) 感谢大佬的解答qwq 小的不胜感激

#include<bits/stdc++.h>
using namespace std;
const int N=30000+10;
int n,p,c;
bool vis[N];
int bo[N];
int dis[N];
int ans=100000000;
queue<int>q;
struct EDGE{
	int v,nxt,w;
}e[N*3];
int head[N],tot;
void add(int x,int y,int z){
	e[++tot].v = y;
	e[tot].nxt = head[x];
	e[tot].w=z;
	head[x]=tot;
}
//int ma[N][N];
void SPFA(int s)
{
	//memset(dis,0x3f,sizeof(dis));数据溢出? 
	for(int i=1;i<=p;i++)
	{
		dis[i]=10000;
	}
	memset(vis,0,sizeof(vis));
	int minn;
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt )
		{
			int vv=e[i].v ;
			if(dis[vv]>dis[u]+e[i].w )
			{
				dis[vv]=dis[u]+e[i].w; 
				if(!vis[vv])
				{
					q.push(vv);
					vis[vv]=1;
				}
			}
		}
	}
}
signed main()
{
	scanf("%d%d%d",&n,&p,&c);
	int x;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&bo[i]);
	}
	int y,z;
	for(int i=1;i<=c;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	for(int i=1;i<=p;i++)
	{
		int res=0;
		SPFA(i);
		for(int i=1;i<=n;i++)
		{
			res+=dis[bo[i]];
		}
		ans=min(ans,res);
	}
	printf("%d",ans);
	return 0;
}
2023/7/11 11:08
加载中...