提交记录

#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
#define int long long
using namespace std;
const int N=2e5+5,M=6e6+5,INF=0x3f3f3f3f;
int n,m,tot,ans,Add;
int head[N],ver[M],Next[M],edge[M],d[N],cnt[N];
bool v[N];

void add(int x,int y,int z){
	ver[++tot]=y;
	edge[tot]=z;
	Next[tot]=head[x];
	head[x]=tot;
}

queue<int> q;

bool spfa(){
	memset(d,INF,sizeof(d));
	q.push(0);
	d[0]=0;
	v[0]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		v[x]=0;
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i],z=edge[i];
			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				cnt[y]=cnt[x]+1;
				if(cnt[y]>=n){
					return false;
				}
				if(!v[y]){
					q.push(y);
					v[y]=1;
				}
			}
		}
	}
	return true;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			add(y,x,0);
			add(x,y,0);
		}
		if(op==2){
			add(y,x,-1);
		}
		if(op==3){
			add(x,y,0);
		}
		if(op==4){
			add(x,y,-1);
		}
		if(op==5){
			add(y,x,0);
		}
	}
	for(int i=1;i<=n;i++){
		add(0,i,0);
	}
	if(!spfa()){
		cout<<-1;
	}
	else{
		for(int i=1;i<=n;i++){
			if(d[i]<0) Add=max(Add,abs(d[i]));
			ans=ans+d[i];
		}
		cout<<ans+(Add+1)*n;
	}
	return 0;
}