POJ 3259 Wormholes——spfa判负环

POJ 3259 Wormholes——spfa判负环

注意不要把正边覆盖！

#include #include #include #include #include #include using namespace std;typedef pair P;const int INF = 0x3f3f3f3f;const int maxn = 505;int T, N, M, W, dis[maxn], vis[maxn], num[maxn];vector

G[maxn];bool spfa() { for (int i = 1; i <= N; i++) dis[i] = INF, vis[i] = 0, num[i] = 0; dis[1] = 0, vis[1] = 1, num[1] = 1; queue q; q.push(1); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].first, val = G[u][i].second; if (dis[v] > dis[u] + val) { dis[v] = dis[u] + val; if (!vis[v]) { vis[v] = 1; q.push(v); num[v]++; if (num[v] > N) return true; } } } } return false;}int main() { scanf("%d", &T); while (T--) { scanf("%d %d %d", &N, &M, &W); for (int i = 1; i <= N; i++) G[i].clear(); for (int i = 1; i <= M; i++) { int u, v, cost; scanf("%d %d %d", &u, &v, &cost); G[u].push_back(make_pair(v, cost)); G[v].push_back(make_pair(u, cost)); } for (int i = 1; i <= W; i++) { int u, v, val; scanf("%d %d %d", &u, &v, &val); G[u].push_back(make_pair(v, -val)); } if (spfa()) printf("YES\n"); else printf("NO\n"); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。