ABC280F并查集图论零环正环思维动脑筋

#include <stdio.h>
#include <string.h>
#define N 100005
int Q, n, m, i, j, k, a, b, c, t, h[N], f[N], u[N];
long long v[N];
struct AB{
    int a, b, c, n;
} d[N*2];
void cun(int a, int b, int c){
    d[++k].a = a, d[k].b = b, d[k].c = c;
    d[k].n = h[a], h[a] = k;
}
void dfs(int a, long long s){
    int b, c, i;
    v[a] = s, f[a] = k;
    for(i=h[a]; i; i=d[i].n){
        b = d[i].b, c = d[i].c;
        if(v[b] < -1e18) dfs(b, v[a]+c);
        else if(v[b] != v[a]+c) u[k] = 1;
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &Q);
    for(i=1; i<=n; i++) v[i]=-5e18;
    for(i=1; i<=m; i++){
        scanf("%d%d%d", &a, &b, &c);
        cun(a, b, c);
        cun(b, a, -c);
    }
    for(k=1; k<=n; k++){
        if(!f[k]) dfs(k, 0);
    }
    while(Q--){
        scanf("%d%d", &a, &b);
        if(f[a] != f[b]) printf("nan\n");
        else if(u[f[a]]) printf("inf\n");
        else printf("%lld\n", v[b]-v[a]);
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
#define N 100005
int Q, n, m, i, j, k, a, b, c, t, h[N], f[N], u[N];
long long v[N];
struct AB{
    int a, b, c, n;
} d[N*2];
void cun(int a, int b, int c){
    d[++k].a = a, d[k].b = b, d[k].c = c;
    d[k].n = h[a], h[a] = k;
}
int find(int x){
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
void dfs(int a, long long s){
    int b, c, i;
    v[a] = s;
    for(i=h[a]; i; i=d[i].n){
        b = d[i].b, c = d[i].c;
        if(v[b] < -1e18) dfs(b, v[a]+c);//没访问过直接赋值
        else if(v[b] != v[a]+c) u[find(a)] = 1;
    }//访问过，如果是零环不需要搜索（重复没必要）
}//如果不是零环，正反方向总有一个正环，必然无穷大，用u打标记
int main(){
    scanf("%d%d%d", &n, &m, &Q);
    for(i=1; i<=n; i++) f[i] = i, v[i]=-5e18;
    for(i=1; i<=m; i++){
        scanf("%d%d%d", &a, &b, &c);
        cun(a, b, c);
        cun(b, a, -c);
        f[find(a)] = find(b);
    }
    for(i=1; i<=n; i++){
        if(i == find(i)) dfs(i, 0);//每个连通块单独预处理
    }
    while(Q--){
        scanf("%d%d", &a, &b);
        if(find(a) != find(b)) printf("nan\n");//不连通
        else if(u[find(a)]) printf("inf\n");//有正环
        else printf("%lld\n", v[b]-v[a]);//a->b，路径唯一相减即可
    }
    return 0;
}