SPFA WA 90pts
查看原帖
SPFA WA 90pts
54372
A_Đark_Horcrux楼主2020/11/29 18:42

第六个点太烦人了……

并问:为什么超级点要从n到1倒序连边?

#include<cstdio>
#include<queue>
using namespace std;
const int N=1e6+10;
inline int read()
{
	int s=0,b=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') b=-1; c=getchar();}
	while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+c-'0',c=getchar();
	return s*b;
}
struct edge{int next,to,dis;}a[N*2];
int n,m,f,s,i; long long ans;
int dis[N],cnt[N],h[N*2]; bool pd,b[N];
inline void build(int x,int y,int z){a[++s]=edge{h[x],y,z},h[x]=s;}
int main()
{
    n=read(),m=read();
    for(i=1;i<=m;i++)
    {
    	f=read(); int x,y,z;
		if(f==1) x=read(),y=read(),build(x,y,0),build(y,x,0);
		else if(f==2)
		{
			x=read(),y=read();
			if(x==y) return !puts("-1");
			build(x,y,1);
		}
		else if(f==3) x=read(),y=read(),build(y,x,0);
		else if(f==4)
		{
			x=read(),y=read();
			if(x==y) return !puts("-1");
			build(y,x,1);
		}
		else if(f==5) x=read(),y=read(),build(x,y,0);
	}
    for(i=n;i>=1;i--) build(0,i,1),dis[i]=-1e9;
    queue<int> q;
    dis[0]=0,b[0]=1,cnt[0]++,q.push(0);
	while(!q.empty())
	{
		int now=q.front();
		q.pop(); b[now]=0;
		for(register int i=h[now];i;i=a[i].next)
		{
			int y=a[i].to; 
			if(dis[y]<dis[now]+a[i].dis)
			{
				dis[y]=dis[now]+a[i].dis;
				if(!b[y])
				{
					b[y]=1,q.push(y),cnt[y]++;
					if(cnt[y]>=n) return !puts("-1");
				}
			}
		}
	}
    for(i=1;i<=n;i++) ans+=dis[i];
    printf("%d",ans);
    return 0;
}
2020/11/29 18:42
加载中...