spfa
可以判断是否有负环,可与 dijkstra 连用
struct edge {
int v, w;
};
vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;
bool spfa(int n, int s) {
memset(dis, 63, sizeof(dis));
dis[s] = 0, vis[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1; // 记录最短路经过的边数
if (cnt[v] >= n) return false;
// 在不经过负环的情况下,最短路至多经过 n - 1 条边
// 因此如果经过了多于 n 条边,一定说明经过了负环
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return true;
}
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
struct{
int v, w, next;
} a[100000];
int head[50000],dis[50000],cnt[50000];
bool vis[50000];
int edge;
queue<int> q;
void add(int u,int v,int w)
{
a[++edge].v = v;
a[edge].w = w;
a[edge].next = head[u];
head[u] = edge;
}
void spfa()
{
memset(dis, 0x3f, sizeof dis);
memset(vis, false, sizeof vis);
memset(cnt, 0, sizeof cnt);
while(!q.empty())
q.pop();
dis[1] = 0;
vis[1] = 1;
q.push(1);
while(q.size())
{
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i;i=a[i].next)
{
int v = a[i].v, w = a[i].w;
if(dis[v]>dis[u]+w)
{
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if(cnt[v]>=n)
{
cout << "YES" << endl;
return;
}
if(!vis[v])
vis[v] = 1, q.push(v);
}
}
}
cout << "NO" << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin >> t;
while(t--)
{
memset(head, 0, sizeof head);///////
cin >> n >> m;
while(m--)
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
if(w>=0)
add(v, u, w);
}
spfa();
}
}