﻿ 题解 UVA11721 Instant View of Big Bang（SPFA建反图判负环）

### 题意

(多组数据 (Tleq125));

### 代码

``````#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e4 + 10;
struct Edge{
int then,to,val;
}e[maxn];

void add(int u, int v, int val){e[++num] = (Edge){head[u], v, val}; head[u] = num;}

void dfs(int p){
mark[p] = 1;
for(int i = head[p]; i; i = e[i].then){
int v = e[i].to;
if(!mark[v]) dfs(v);
}
}

void SPFA(int st){
queue<int> q;
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
dis[st] = 0; vis[st] = 1; q.push(st);
while(!q.empty()){
int u = q.front();
q.pop(); vis[u] = 0;
for(int i = head[u]; i; i = e[i].then){
int v = e[i].to;
if(mark[v]) continue;
if(dis[v] > dis[u] + e[i].val){
dis[v] = dis[u] + e[i].val;
if(!vis[v]){
cnt[v] ++;
if(cnt[v] > n) flag = 1, dfs(v);
//注意：这里是 >n 而不是 >=n 例如：只有一个点时
q.push(v);
vis[v] = 1;
}
}
}
}
}

int main(){
int T;
scanf("%d", &T);
for(int t = 1; t <= T; ++ t){
num = 0; flag = 0;
memset(mark,0,sizeof(mark));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i){
int u,v,val;
scanf("%d%d%d", &u, &v, &val);
}
for(int i = 0; i < n; ++ i) add(n, i, 0);
SPFA(n);
printf("Case %d:", t);
if(!flag) printf(" impossible
");  //注意空格，换行
else{
for(int i = 0; i < n; ++ i)
if(mark[i]) printf(" %d", i);
printf("
");
}
}
return 0;
}
``````