在我对 SPFA 使用了 SLF 优化之后，我喜提 #11 WA，这大抵就是出题人的毒瘤 hack 数据吧

但我很不理解，为什么 SPFA 不能使用 SLF 优化？为什么使用了就会在误判负环？

#include <bits/extc++.h>

#define inline						__always_inline
#define init_buf(l, r, buf, val)	for (auto m_it = l; m_it <= r; m_it++)	buf[m_it] = val
#define INF		1000000000l
#define cin		std::cin
#define cout	std::cout

template <typename key_t, typename cmp_fn>
using priority_queue = __gnu_pbds::priority_queue<key_t, cmp_fn>;
using pii = std::pair<int, int>;

int n, m;
int u, v, w;

struct edge_t
{
	int w;
	int v, tail;
};
edge_t edge[10000];
int head[3001], top = 1;
char visit[3001];

inline void add_edge(int u, int v, int w)
{
	edge[top] = {w, v, head[u]};
	head[u] = top++;
}

int h[3001];
void SPFA(int s = 0)
{
	int count[n + 1];
	init_buf(0, n, count, 0);
	init_buf(0, n, h, INF);	h[s] = 0;
	std::deque<int> queue;
	queue.push_back(s);
	while (!queue.empty())
	{
		auto u = queue.front();
		queue.pop_front();
		visit[u] = 0;
		for (int e = head[u]; e; e = edge[e].tail)
		{
			int v = edge[e].v, w = edge[e].w;
			if (h[v] - h[u] > w)
			{
				h[v] = h[u] + w;
				if (!visit[v])
				{
					visit[v] = 1;
					count[v]++;
					if (count[v] == n + 1)
						cout << "-1", exit(0);
					queue.push_back(v);
					// if (queue.empty() || h[v] < h[queue.front()])
					// 	queue.push_front(v);
					// else
					// 	queue.push_back(v);
				}
			}
		}
	}
	for (int u = 1; u <= n; u++)
		for (int e = head[u]; e; e = edge[e].tail)
			edge[e].w += h[u] - h[edge[e].v];
}

int dis[3001][3001];
priority_queue<pii, std::greater<pii>> pq;
decltype(pq)::point_iterator its[3001];

inline void Dijkstra(int s)
{
	int *row = dis[s];
	init_buf(1, n, row, INF);	row[s] = 0;
	init_buf(1, n, its, pq.push({row[m_it], m_it}));
	init_buf(1, n, visit, 0);
	while (!pq.empty())
	{
		auto u = pq.top().second;
		pq.pop();
		visit[u] = 1;
		for (int e = head[u]; e; e = edge[e].tail)
		{
			int v = edge[e].v, w = edge[e].w;
			if (!visit[v] && row[v] - row[u] > w)
			{
				row[v] = row[u] + w;
				pq.modify(its[v], {row[v], v});
			}
		}
	}
}

inline void print_graph()
{
	for (int u = 1; u <= n; u++)
	{
		cout << u << " | ";
		for (int e = head[u]; e; e = edge[e].tail)
			cout << '(' << edge[e].v << ", " << edge[e].w << ") ";
		cout << '\n';
	}
}

int main()
{
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v >> w;
		add_edge(u, v, w);
	}
	for (int i = 1; i <= n; i++)
		add_edge(0, i, 0);
	SPFA();
	for (int i = 1; i <= n; i++)
		Dijkstra(i);
	for (int u = 1; u <= n; u++)
	{
		int64_t ans = 0;
		for (int v = 1; v <= n; v++)
		{
			if (dis[u][v] == INF)
				ans += (int64_t)v * INF;
			else
				ans += (int64_t)v * (int64_t)(dis[u][v] - h[u] + h[v]);
		}
		cout << ans << '\n';
	}
	return 0;
}