题目链接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499
题意：就是判断图中有无负环 SPFA,某个节点入队次数大于n就是有负环。
代码：
;const int MAXN = 41000;const int INF = 0x3f3f3f3f;struct Edge{int v;int cost;Edge(int _v = 0, int _cost = 0){v = _v;cost = _cost;}};vector<Edge> E[MAXN];void addedge(int u, int v, int cost){E[u].push_back(Edge(v, cost));}bool vis[MAXN];int cnt[MAXN];//记录入队列的次数int dist[MAXN];////////////////bool SPFA(int start, int n){memset(vis, false, sizeof(vis));memset(cnt, 0, sizeof(cnt));for (int i = 0; i <= n; i++) dist[i] = INF;vis[start] = true;dist[start] = 0;queue<int> que;while (!que.empty()) que.pop();que.push(start);cnt[start] = 1;while (!que.empty()){int u = que.front(); que.pop();vis[u] = false;for (int i = 0; i<E[u].size(); i++){int v = E[u][i].v;if (dist[v]>dist[u] + E[u][i].cost){dist[v] = dist[u] + E[u][i].cost;if (!vis[v]){vis[v] = true;que.push(v);cnt[v]++;if (cnt[v] > n) return false;}}}}return true;}int n, m;int a, b, c;int main(){int t;scanf(“%d”,&t);while (t–){scanf(“%d%d”,&n,&m);for (int i = 0; i <= n; i++) E[i].clear();while (m–){scanf(“%d%d%d”, &a, &b, &c);addedge(a, b, c);//addedge(b, a, c);}if (!SPFA(0, n)) puts(“possible”);else puts(“not possible”);}return 0;}
，不如意的时候不要尽往悲伤里钻，想想有笑声的日子吧
