RT，因为有人用裸 SPFA 开 O2 过了本题，然而事实上它没有办法通过$\,p_i=1\,$的简单数据，数据生成器：

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

int main()
{
	int n = 30000, m = 30000, p = 1;
	printf("%d %d\n", n, m);
	for (int i = 1; i <= m; ++ i)
		printf("%d %d\n", i - 1, p);
	return 0;
}

用这个代码本机 -Ofast 实测跑 2061 ~ 2097 ms