https://www.luogu.com.cn/discuss/969457 (01bfs)

(这是spfa Unaccepted 100pts)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 10;
int n,k,idx = 1,tot;
int head[MAXN],dis[MAXN],cnt[MAXN];
bool vis[MAXN];
struct node{
	int v,w,nxt;
}edge[MAXN];
inline void add(int u,int v,int w)
{
	edge[idx].v = v;
	edge[idx].w = w;
	edge[idx].nxt = head[u];
	head[u] = idx ++;
}
inline void spfa(int s)
{
	queue<int>q;
	for(int i = 1;i <= n;i ++)
	{
		dis[i] = 1;
		vis[i] = 1;
		q.push(i);
	}
	int tot = 0;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = 0;
		tot ++;
		if(tot >= 2e7)
		{
			cout << "-1" << endl;
			exit(0);
		}
		for(int i = head[u];i;i = edge[i].nxt)
		{
			int v = edge[i].v,w = edge[i].w;
			if(dis[v] < dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if(!vis[v])
				{
					cnt[v] ++;
					if(cnt[v] > n)
					{
						cout << "-1" << endl;
						exit(0);
					}
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i = 1;i <= k;i ++)
	{
		int x,u,v;
		cin >> x >> u >> v;
		if(x == 1)
		{
			add(u,v,0);
			add(v,u,0);
		}
		if(x == 2)
		{
			if(u == v)
			{
				cout << "-1" << endl;
				return 0;
			}
			add(u,v,1);
		}
		if(x == 3)
			add(v,u,0);
		if(x == 4)
		{
			if(u == v)
			{
				cout << "-1" << endl;
				return 0;
			}
			add(v,u,1);
		}
		if(x == 5)
			add(u,v,0);
	}
	for(int i = 1;i <= n;i ++) add(0,i,0);
	spfa(0);
	int Ans = 0;
	for(int i = 1;i <= n;i ++) Ans += dis[i];
	cout << Ans << endl;
	return 0;
}