或者文章也行
by __gcd @ 2020-01-22 10:20:30
入队次数来判
by 十十十十 @ 2020-01-22 10:21:18
如有点入队次数超过n，则有环（最短路负环，反之）。
by A1443356159 @ 2020-01-22 10:22:33
@[十十十十](/user/153802)
然后这玩意只有10分
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_INT = (1 << 30);
const ll MAX_LONG = ((ll)1 << (ll)60);
struct In
{
template <typename T>
inline In& operator >> (T &x)
{
char c = getchar();
int op = 0; x = 0;
while(c ^ '-' && !isdigit(c))c = getchar();
if(c == '-')op = 1, c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
if(op)x = -x;
return *this;
}
} in;
const int N = 10010;
const int INF = 2147483647;
struct Edge
{
int to, w;
};
int n, m;
int dis[N], times[N];
bool vis[N];
vector<Edge> nbr[N];
void init()
{
memset(times, 0, sizeof(times));
for(int i = 1; i <= n; i++)
{
nbr[i].clear();
}
return ;
}
bool spfa()
{
queue<int> q;
for(int i = 1; i <= n; i++)
{
dis[i] = INF;
}
dis[1] = 0;
vis[1] = true;
q.push(1);
times[1]++;
while(q.empty() == false)
{
int cur = q.front();
q.pop();
vis[cur] = false;
for(int i = 0; i < nbr[cur].size(); i++)
{
int v = nbr[cur][i].to;
int w = nbr[cur][i].w;
if(dis[cur] + w < dis[v])
{
dis[v] = dis[cur] + w;
if(vis[v] == false)
{
q.push(v);
vis[v] = true;
times[v]++;
}
if(times[v] > n)return false;
}
}
}
return true;
}
int main()
{
int t;
in >> t;
while(t--)
{
in >> n >> m;
init();
for(int i = 1; i <= m; i++)
{
int u, v, w;
in >> u >> v >> w;
nbr[u].push_back((Edge){v, w});
}
bool ans = spfa();
if(ans == false)cout << "YE5" << endl;
else cout << "N0" << endl;
}
return 0;
}
```
by __gcd @ 2020-01-22 10:23:02
把 vis 数组去掉
by Lucky_Xiang @ 2020-01-22 10:31:22
提高的那本书上有的，spfa单点入队次数超过n是一种，有大环会T，一般的处理方法是
```cpp
if((double)clock()/CLOCKS_PER_SEC>0.9) exit(printf("有环")&0);
```
或者写dfs版的spfa，如果dfs栈内有当前节点且权变小就有负环
by bessie_goes_moo @ 2020-01-22 10:37:17
@[幸运翔](/user/120742) 还是10分
by __gcd @ 2020-01-22 10:41:00
@[bessie_goes_moo](/user/125322) 目前只会bfs
by __gcd @ 2020-01-22 10:41:43
@[一只大头](/user/149192) 在进行 SPFA 时，用一个数组 $cnt_i $来标记每个顶点入队次数。如果一个顶点入队次数 $cnt_i$ 大于顶点总数 $n$，则该图包含负环。
by Stephen_Curry @ 2020-01-22 10:58:52
参考代码：
```cpp
const int inf = 0x3f3f3f3f;
struct node {
int v, w;
node() {
}
node(int vv, int ww) {
v = vv;
w = ww;
}
};
vector<node> g[N];
int n, m, s;
int d[N], cnt[N];
bool in_queue[N];
queue<int> q;
bool spfa(int s) {
memset(d, 0x3f, sizeof(d));
d[s] = 0;
in_queue[s] = true;
q.push(s);
cnt[s]++;
while (!q.empty()) {
int v = q.front();
q.pop();
in_queue[v] = false;
for (int i = 0; i < g[v].size(); i++) {
int x = g[v][i].v;
if (d[x] > d[v] + g[v][i].w) {
d[x] = d[v] + g[v][i].w;
if (!in_queue[x]) {
q.push(x);
in_queue[x] = true;
cnt[x]++;
if (cnt[x] > n) {
return true;
}
}
}
}
}
return false;
}
```
by Stephen_Curry @ 2020-01-22 11:00:42