$\quad \rm RT$

$\quad$这是最短路的代码，只有 $70\rm pts.$

#include<bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; i++)

const int N = 1e5 + 10;

int n, m, op, u, v, in[N], dis[N], cnt[N];
int last[N], to[N << 2], W[N << 2], Next[N << 2], tot;
queue <int> Q;

void add (int u, int v, int w) {
	to[++tot] = v, W[tot] = w, Next[tot] = last[u], last[u] = tot;
}

int main () {

	scanf("%d%d", &n, &m);
	while (m--) {
		scanf("%d%d%d", &op, &u, &v);
		if (op == 1) add(u, v, 0), add(v, u, 0);
		else if (op == 2) add(v, u, -1);
		else if (op == 3) add(u, v, 0);
		else if (op == 4) add(u, v, -1);
		else if (op == 5) add(v, u, 0);
		
	}
	rep(i, 1, n) to[++tot] = i, Next[tot] = last[0], last[0] = tot;
	
	memset(dis, 0x3f, sizeof dis);
	dis[0] = 0, in[0] = true, Q.push(0);
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop(), in[u] = false;
		if (++cnt[u] > 1000) puts("-1"), exit(0);
		for (int i = last[u]; i; i = Next[i])
			if (dis[to[i]] > dis[u] + W[i]) {
				dis[to[i]] = dis[u] + W[i];
				if (!in[to[i]]) Q.push(to[i]);
			}
	}
	
	long long ans = 0; int Min = 1e9;
	rep(i, 1, n) Min = min(Min, dis[i]);
	rep(i, 1, n) ans += dis[i] - Min;
	printf("%lld\n", ans + n);

	return 0;
}

$\quad$这是最长路的代码，$\rm AC$ 了

#include<bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; i++)

const int N = 1e5 + 10;

int n, m, op, u, v, in[N], dis[N], cnt[N];
int last[N], to[N << 2], W[N << 2], Next[N << 2], tot;
queue <int> Q;

void add (int u, int v, int w) {
	to[++tot] = v, W[tot] = w, Next[tot] = last[u], last[u] = tot;
}

int main () {

	scanf("%d%d", &n, &m);
	while (m--) {
		scanf("%d%d%d", &op, &u, &v);
		if (op == 1) add(u, v, 0), add(v, u, 0);
		else if (op == 2) add(u, v, 1);
		else if (op == 3) add(v, u, 0);
		else if (op == 4) add(v, u, 1);
		else if (op == 5) add(u, v, 0);
		
	}
	for (int i = n; i >= 1; i--) add(0, i, 1);
	
	memset(dis, 128, sizeof dis);
	dis[0] = 0, in[0] = true, Q.push(0);
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop(), in[u] = false;
		if (++cnt[u] > 3500) puts("-1"), exit(0);
		for (int i = last[u]; i; i = Next[i])
			if (dis[to[i]] < dis[u] + W[i]) {
				dis[to[i]] = dis[u] + W[i];
				if (!in[to[i]]) Q.push(to[i]);
			}
	}
	
	long long ans = 0;
	rep(i, 1, n) ans += dis[i];
	printf("%lld\n", ans);

	return 0;
}