首页 > 代码库 > UVA 558 Wormholes
UVA 558 Wormholes
利用SPFA判负环。如果一个节点出队N次有负环这里记录一下
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}int cnt[1010];bool inq[1010];int d[1010];int w[1010][1010],N,M;vector<int>G[1010];queue<int>q;bool SPFA(){ memset(cnt,0,sizeof(cnt)); memset(inq,false,sizeof(inq)); memset(d,0x3f,sizeof(d)); while (!q.empty()) q.pop(); q.push(0); cnt[0]++; inq[0] = true; d[0] = 0; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = 0; i < (int)G[u].size(); i++) { int v = G[u][i]; if (d[v] > d[u] + w[u][v]) { d[v] = d[u] + w[u][v]; if (!inq[v]) { inq[v] = true; cnt[v]++; if (cnt[v] >= N) return true; q.push(v); } } } } return false;}int main(){ //freopen("sample.txt","r",stdin); int T; scanf("%d",&T); while (T--) { scanf("%d%d",&N,&M); for (int i = 0; i < 1010; i++) G[i].clear(); while (M--) { int u,v,we; scanf("%d%d%d",&u,&v,&we); G[u].push_back(v); w[u][v] = we; } if (SPFA()) puts("possible"); else puts("not possible"); } return 0;}
UVA 558 Wormholes
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。