（蒟蒻只会写普通SPFA，正解的算法还没学过QwQ）

//使用vector存图
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int R = 1e5 + 10;
struct Node
{
	int p, len;
};
vector<Node> v[R];
int cnt[R];
ll dis[R];
bool b[R];
class Stack
{
public:
	int top_ = 0, a[R << 2];
	void push(int x) { ++top_, a[top_] = x; }
	void pop() { --top_; }
	bool empty() { return !top_; }
	int top() { return a[top_]; }
} q;
ll spfa(int n)
{
	memset(dis, -0x3f, sizeof(dis));
	dis[0] = 0;
	b[0] = true;
	q.push(0);
	cnt[0] = 0;
	int from, to, sz;
	register int j;
	while (!q.empty())
	{
		from = q.top();
		q.pop();
		b[from] = false;
		sz = v[from].size();
		for (j = 0; j < sz; ++j)
		{
			to = v[from][j].p;
			if (dis[from] + v[from][j].len > dis[to])
			{
				dis[to] = dis[from] + v[from][j].len;
				cnt[to] = cnt[from] + 1;
				if (cnt[to] > n)
				{
					return -1;
				}
				if (!b[to])
				{
					q.push(to);
					b[to] = true;
				}
			}
		}
	}
	ll ans = 0;
	for (j = 1; j <= n; ++j)
	{
		ans += dis[j];
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// freopen("test.txt", "r", stdin);
	int n, k, x, y;
	char opt;
	cin >> n >> k;
	register int j;
	for (j = 1; j <= k; ++j)
	{
		cin >> opt >> x >> y;
		if (opt == '1') // x==y -> x>=y+0 && y>=x+0
		{
			v[x].push_back({y, 0});
			v[y].push_back({x, 0});
		}
		else if (opt == '2') // x<y -> x<=y-1 -> y>=x+1
		{
			v[x].push_back({y, 1});
		}
		else if (opt == '3') // x>=y -> x>=y+0
		{
			v[y].push_back({x, 0});
		}
		else if (opt == '4') // x>y -> x>=y+1
		{
			v[y].push_back({x, 1});
		}
		else // opt=='5' // x<=y -> y>=x+0
		{
			v[x].push_back({y, 0});
		}
	}
	for (j = 1; j <= n; ++j)
	{
		v[0].push_back({j, 1}); // dis[j]>=dis[0]+1
	}
	cout << spfa(n);
	return 0;
}

使用vector吸氧也不能过

//使用邻接表存图
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int R = 1e5 + 10;
struct Node
{
	int to, len, next;
} edge[(R << 1) + R];
int pre[R], tot = 0;
int cnt[R];
ll dis[R];
bool b[R];
class Stack
{
public:
	int top_ = 0, a[R << 1];
	void push(int x) { ++top_, a[top_] = x; }
	void pop() { --top_; }
	bool empty() { return !top_; }
	int top() { return a[top_]; }
} q;
inline void add(int x, int y, int len)
{
	++tot;
	edge[tot].to = y;
	edge[tot].len = len;
	edge[tot].next = pre[x];
	pre[x] = tot;
}
ll spfa(int n)
{
	memset(dis, -0x3f, sizeof(dis));
	dis[0] = 0;
	b[0] = true;
	q.push(0);
	cnt[0] = 0;
	int from, to;
	register int j;
	while (!q.empty())
	{
		from = q.top();
		q.pop();
		b[from] = false;
		for (j = pre[from]; j; j = edge[j].next)
		{
			to = edge[j].to;
			if (dis[from] + edge[j].len > dis[to])
			{
				dis[to] = dis[from] + edge[j].len;
				cnt[to] = cnt[from] + 1;
				if (cnt[to] > n)
				{
					return -1;
				}
				if (!b[to])
				{
					q.push(to);
					b[to] = true;
				}
			}
		}
	}
	ll ans = 0;
	for (j = 1; j <= n; ++j)
	{
		ans += dis[j];
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// freopen("test.txt", "r", stdin);
	int n, k, x, y;
	char opt;
	cin >> n >> k;
	register int j;
	for (j = 1; j <= k; ++j)
	{
		cin >> opt >> x >> y;
		if (opt == '1') // x==y -> x>=y+0 && y>=x+0
		{
			add(x, y, 0);
			add(y, x, 0);
		}
		else if (opt == '2') // x<y -> x<=y-1 -> y>=x+1
		{
			add(x, y, 1);
		}
		else if (opt == '3') // x>=y -> x>=y+0
		{
			add(y, x, 0);
		}
		else if (opt == '4') // x>y -> x>=y+1
		{
			add(y, x, 1);
		}
		else // opt=='5' // x<=y -> y>=x+0
		{
			add(x, y, 0);
		}
	}
	for (j = 1; j <= n; ++j)
	{
		add(0, j, 1); // dis[j]>=dis[0]+1
	}
	cout << spfa(n);
	return 0;
}

邻接表能过

提交记录

请问这是为什么呢