蒟蒻求助!
查看原帖
蒟蒻求助!
98881
ijktmn楼主2020/5/5 12:17

为何50分?

code:

#include<bits/stdc++.h>
using namespace std;
const int Maxm=500010;
const int Maxn=100010;
typedef long long ll;
struct Edge
{
    int next,to,v;
}e[Maxm];
int n,m,cnt=0;
int dis[Maxn],vis[Maxn],q[Maxn+10],cir[Maxn],head[Maxn];
void adde(int u,int v,int w)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].v=w;
	head[u]=cnt;
}
bool SPFA()
{
	memset(cir,0,sizeof(cir));
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	vis[0]=1;
	int l=0,r=n;
	q[0]=0;
	cir[0]=1;
	while(l!=r)
	{
		int now=q[l];
		l++;
		if(l==Maxn) l=0;
		for(int i=head[now];i;i=e[i].next)
		{
			if(dis[now]+e[i].v>dis[e[i].to])
			{
				dis[e[i].to]=dis[now]+e[i].v;
				if(++cir[e[i].to]>=n) return false;
				if(!vis[e[i].to])
				{
					vis[e[i].to]=1;
					q[r++]=e[i].to;
					if(r==Maxn) r=0;
				}
			}
		}
		vis[now]=0;
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int op,u,v;
		scanf("%d%d%d",&op,&u,&v);
		switch(op)
		{
			case 1:{
				adde(u,v,0);
				adde(v,u,0);
				break;
			}
			case 2:{
				if(u==v)
				{
					printf("-1");
					return 0;
				}else{
					adde(u,v,1);
				}
				break;
			}
			case 3:{
				adde(v,u,0);
				break;
			}
			case 4:{
				if(u==v)
				{
					printf("-1");
					return 0;
				}else{
					adde(v,u,1);
				}
				break;
			}
			case 5:{
				adde(u,v,0);
				break;
			}
		}
	}
	for(int i=n;i>0;i--)
	{
		adde(0,i,1);
	}
	if(!SPFA())
	{
		printf("-1");
		return 0;
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=dis[i];
	}
	printf("%lld",ans);
	return 0;
}

2020/5/5 12:17
加载中...