AcWing 852. spfa判断负环 边权可能为负数。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = , M = ;
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N];//最短距离
int cnt[N];//当前最短路的边数,如果大于等于n,那么有负环
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa() {
queue<int> q;
for (int i = ; i <= n; i ++ ) {
st[i] = true;//可能负环1到不了,那么就把所有的点加进去
q.push(i);
}
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + ;
if (cnt[j] >= n) return true;
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -, sizeof h);
while (m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
if (spfa()) puts("Yes");
else puts("No");
return ;
}

文章来源地址https://www.yii666.com/article/756137.html文章地址https://www.yii666.com/article/756137.html网址:yii666.com<网址:yii666.com文章来源地址:https://www.yii666.com/article/756137.html

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png