題目鏈接

題意

問是否存在負環

AC

因為Dijkstra不能處理帶有負邊權的圖，可以用spfa 和 BellmenFord

• spfa

using namespace std; int inf = 0x3f3f3f3f; struct ac{int v, c; }; int dis[N], cnt[N]; bool vis[N]; vector<ac> g[N]; bool spfa(int start , int n) {mem(cnt, 0);mem(dis, inf);mem(vis, false);dis[start] = 0;queue<int> que;// 將源點入隊que.push(start);vis[start] = true;cnt[start] = 1;while (!que.empty()) {int u = que.front();que.pop();vis[u] = false;for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i].v;int c = g[u][i].c;if (dis[v] > dis[u] + c) {dis[v] = dis[u] + c;// 更新的點是否已經入隊if (vis[v] == false) {vis[v] = true;que.push(v);// 入隊大于 n 次，存在負環if (++cnt[v] > n) return true;}}}}return false; }int main(){freopen("in.txt", "r", stdin);int n, m, w;int t;cin >> t;while (t--) {cin >> n >> m >> w;for (int i = 0; i < m; ++i) {int u, v, c;cin >> u >> v >> c;g[u].push_back((ac){v, c});g[v].push_back((ac){u, c});}for (int i = 0; i < w; ++i) {int u, v, c;cin >> u >> v >> c;g[u].push_back((ac){v, -c});}if (spfa(1, n)) cout << "YES\n";else cout << "NO\n";for (int i = 0; i <= n; ++i) {g[i].clear();}}return 0; }

總結

以上是生活随笔為你收集整理的POJ 3259 Wormholes的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。