abc280F - Pay or Receive（判断是否全为零环）

https://atcoder.jp/contests/abc280/tasks/abc280_f

对于每一个连通块单独处理，首先判断是否全为0环，可以用bfs判断。
从一个点出发计算其他点到它的最短距离，如果存在一个不唯一，说明存在非零环。

然后计算距离的时候直接-d[x]+d[y]即可

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const ll inf=1ll<<60;
const int N=1e6+5;
ll nex[N*2],head[N],to[N*2],tot,w[N*2],d[N],cnt;
ll bz[N],b[N];
ll n,m,Q,x,y,z;
bool vis[N];
queue<int> q;
void add(ll x,ll y,ll z){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot; w[tot]=z;
}
void bfs(int s){
	while (!q.empty()) q.pop();
	
	b[s]=++cnt;
	q.push(s);
	vis[s]=1;
	while (!q.empty()) {
		x=q.front(); q.pop();
		for (int i=head[x];i;i=nex[i]) {
			int v=to[i];
			if (!vis[v]) {
				vis[v]=1;
				d[v]=d[x]+w[i];
				q.push(v);
				b[v]=cnt;
			}
			if (d[v]!=d[x]+w[i]) bz[cnt]=1;
		}
	}
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	
	scanf("%lld %lld %lld",&n,&m,&Q);
	fo(i,1,m) {
		scanf("%lld %lld %lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,-z);
	}
	
	fo(i,1,n) {
		if (!vis[i]) {
			bfs(i);
		}
	}
	
	
	while (Q--) {
		scanf("%lld %lld",&x,&y);
		if (b[x]^b[y]) puts("nan");
		else if (bz[b[x]]) puts("inf");
		else printf("%lld\n",-d[x]+d[y]);
	}

	return 0;
}