提问(玄关)
  • 板块P2648 赚钱
  • 楼主zzh_KM
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/2 12:10
  • 上次更新2024/9/2 20:09:03
查看原帖
提问(玄关)
786861
zzh_KM楼主2024/9/2 12:10

已AC,但不知道之前WA60pts的原理(所有需要输出orz的点都没有输出orz)

SPFA代码如下:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll d,p,c,f,a,b,t,cnt,zzh,ans=1E18,head[500],flag[500],dis[500],num[500];//num是判断负环所用记录出队次数的数组
queue<ll>q;
struct node
{
	ll nxt,to,val;
}e[2000];
void add(ll u,ll v,ll w)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	e[cnt].val=w;
	head[u]=cnt;
}
bool spfa()
{
	ll x,v;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		flag[x]=0;
		num[x]++;
		if(num[x]>c-1)return 0;//有负环
		for(int i=head[x];i;i=e[i].nxt)
		{
			v=e[i].to;
			if(dis[x]+e[i].val<dis[v])
			{
				dis[v]=dis[x]+e[i].val;
				if(flag[v]==0)
				{
					flag[v]=1;
					q.push(v);
				}
			}
		}
	}
	return 1;
}
int main()
{
	cin>>d>>p>>c>>f;
	for(int i=1;i<=p;i++)
	{
		cin>>a>>b;
		add(a,b,-d);
	}
	for(int i=1;i<=f;i++)
	{
		cin>>a>>b>>t;
		add(a,b,t-d);
	}
	for(zzh=1;zzh<=c;zzh++)
	{
		for(int j=1;j<=499;j++)dis[j]=1E18;
		dis[zzh]=-d; flag[zzh]=1;
		q.push(zzh);
		memset(num,0,sizeof num);//60pts时落下了这一句 
		if(!spfa())break;
		for(int j=1;j<=c;j++)
			ans=min(ans,dis[j]);
		while(!q.empty())q.pop();
	}
	if(zzh>c)cout<<-ans;
	else cout<<"orz";
	return 0;
}

如注释,多测不清空,爆零两行泪,但是讲道理num应该会不断累加,导致一进spfa函数就跳出输出orz,为何反而不输出orz呢?

2024/9/2 12:10
加载中...