快noip了我还在干什么啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
来我们看这道题
根据条件建图， 因为求得是最小值， 所以要跑最长路qwq（这是我记住的QAQ
不想写了让我们直接看看题解吧！
（five20的题解）
有环代表条件冲突， 输出“-1”
建源点的时候反向建会快（这就很妙了
1 #include2 #include 3 #include 4 #include 5 #define ri register int 6 #define ll long long 7 using namespace std; 8 const int sz = 200010; 9 int n, k, num = 0;10 ll ans;11 int head[sz], dis[sz], tot[sz];12 bool flag;13 bool vis[sz];14 struct edge {15 int nxt, to, dis;16 }e[sz << 1];17 inline int read() {18 char ch = getchar(); int x = 0, f = 1;19 while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar();}20 while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0' ; ch = getchar();}21 return x * f;22 }23 void add(int from, int to, int dis) {24 e[++num].nxt = head[from];25 e[num].to = to;26 e[num].dis = dis;27 head[from] = num;28 }29 void spfa() {30 queue q;31 q.push(0);32 vis[0] = 1;33 while(!q.empty()) {34 int u = q.front();35 q.pop();36 if(tot[u] == n - 1) {37 printf("-1");38 exit(0);39 }40 vis[u] = 0;41 tot[u]++;42 for(ri i = head[u]; i; i = e[i].nxt) {43 int v = e[i].to;44 if(dis[v] < dis[u] + e[i].dis) {45 dis[v] = dis[u] + e[i].dis;46 if(!vis[v]) {47 vis[v] = 1;48 q.push(v);49 }50 }51 }52 }53 }54 int main() {55 scanf("%d%d", &n, &k);56 for(ri i = 1; i <= k; i++) {57 int opt = read(), u = read(), v = read();58 if(opt == 1) {59 add(v, u, 0);60 add(u, v, 0);61 }62 else if(opt == 2) {63 if(u == v) {64 flag = 1;65 break;66 }67 else add(u, v, 1);68 }69 else if(opt == 3) add(v, u, 0);70 else if(opt == 4) {71 if(u == v) {72 flag = 1;73 break;74 }75 else add(v, u, 1);76 }77 else if(opt == 5) add(u, v, 0);78 }79 if(flag == 1) {80 printf("-1");81 return 0;82 }83 for(ri i = n; i >= 1; i--) add(0, i, 1);84 spfa();85 for(ri i = 1; i <= n; i++) 86 ans += dis[i];87 printf("%lld", ans);88 return 0;89 }90 /*91 4 792 1 3 293 2 2 494 5 1 395 3 4 296 3 2 397 4 3 198 5 1 499 */