已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呢?