蒟蒻刚学OI,求助
查看原帖
蒟蒻刚学OI,求助
164294
Oct0pus楼主2020/11/3 00:11

WA2个点,TLE1个点,求助

#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>
using namespace std;
#define L 200010
typedef long long ll;
struct edge{
	int to,nxt;
	ll w;
}e[L];
int head[L],ind[L];
ll dis[L];
bool vis[L];
int n,m,sz;
queue<int> q;
inline int read(void){
	int f=1,x=0;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(int)ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline int add(int u,int v,ll w){
	e[sz].to=v;
	e[sz].w=w;
	e[sz].nxt=head[u];
	head[u]=sz++;
}
inline bool spfa(void){
	memset(dis,-1,sizeof(dis));
	ind[0]=1;dis[0]=0;vis[0]=true;
	q.push(0);
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=false;
		for(int i=head[u];~i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v]<dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				if(!vis[v]){
					vis[v]=true;
					q.push(v);
					ind[v]++;
					if(ind[v]==n+1)return false;
				}
			}
		}
	}
	return true;
}
int main(){
	memset(head,-1,sizeof(head));
	n=read();m=read();
	while(m--){
		int a=read(),u=read(),v=read();
		if(a==1){add(v,u,0);add(u,v,0);}
		else if(a==2){
			if(v==u){printf("-1");return 0;}
			add(u,v,1);
		}
		else if(a==3)add(v,u,0);
		else if(a==4){
			if(v==u){printf("-1");return 0;}
			add(v,u,1);
		}
		else add(u,v,0);
	}
	for(int i=1;i<=n;i++)add(0,i,1);
	ll ans=0;
	if(!spfa())printf("-1");
	else for(int i=1;i<=n;i++)ans+=dis[i];
	printf("%d",ans);
	return 0;
}
2020/11/3 00:11
加载中...