Cu Ball
```cpp
#include <bits/stdc++.h>
#define inf 0x3fffffff
using namespace std;
const int N = 1e5 + 5;
int n, m, s, t, u, v, k, w, op;
struct edge {
int v, w;
};
vector<edge> e[N];
stack<int> q;
int dis[N], vis[N], cnt[N], b[N];
bool F = 1;
void SPFA(int s) {
q.push(s), vis[s] = 1, dis[s] = 0;
while(q.size()) {
int u = q.top();
q.pop();
vis[u] = 0, b[u] = 1;
for(auto ed : e[u]) {
int v = ed.v, w = ed.w;
if(dis[v] < dis[u] + w) {
cnt[v] = cnt[u] + 1, dis[v] = dis[u] + w;
if(cnt[v] > n) {
F ^= 1, cout << -1;
return;
}
if(!vis[v])
q.push(v), vis[v] = 1;
}
}
}
}
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(!(c >= '0' && c <= '9')) {
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0', c = getchar();
return x * f;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(nullptr), cout.tie(nullptr);
// freopen("std.in", "r", stdin);
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
op = read(), u = read(), v = read();
if(op == 1)
e[u].push_back({v, 0}), e[v].push_back({u, 0});
else if(op == 2)
e[u].push_back({v, 1});
else if(op == 3)
e[v].push_back({u, 0});
else if(op == 4)
e[v].push_back({u, 1});
else
e[u].push_back({v, 0});
}
for(int i = 1; i <= n; ++i)
e[0].push_back({i, 0}), dis[i] = -inf;
SPFA(0);
if(F ^ 1)
return 0;
int ans = 0;
for(int i = 1; i <= n; ++i)
ans += dis[i] + 1;
cout << ans;
return 0;
}
```
@[zxjn](/user/891168) 已知的优化：
- `queue` 换成 `stack`。
- `if` 比 `switch` 快。
- 要用 `cin` 就加个 `ios::sync_with_stdio(0)`。
by Walrus @ 2024-03-16 14:19:52
@[Walrus](/user/908424) ok
by zxjn @ 2024-03-16 14:24:54