ABC280F

Magus · 2026-03-25 20:38:33 · 题解

校内模拟赛考到了，成功被硬控。

下面把询问的起点称为 u，终点称为 v。

我们知道，由于是双向边，所以一个连通块一定是一个强连通分量。所以 nan 的条件就是 u 和 v 不在同一个连通块内，用并查集维护即可。

能无限增加肯定就是该连通块内存在正环，这个结论可以推广到该连通块内存在负环也能无限增加。因为有一条反向边一定就会有一条正向边，所以有负环就一定有正环。

把这些排除在外，那什么样的情况下有解呢？

把以上的都排除，我们就知道了，有解的情况下环对答案是没有影响的。即该连通块内只有零环或没有环。没有环时，u 到 v 是只有一条路径的。有零环时，u 到 v 虽然有不止一条路径，但零环对答案没有任何影响，所以有解时，u 到 v 的距离是一定的。

根据以上结论，我们可以选择这个连通块内任意一个点来遍历整个连通块，类似于做一个最短路的过程，我们如果遍历到两条路径的距离不一样，那么就是 inf 的情况，否则答案即为 dis_v-dis_u。

#include<bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define I using
#define AK namespace
#define CSPS2026 std
I AK CSPS2026;
const int maxn=1e6+10,maxm=1e3+10,mod=998244353;
int t,n,m,x,y,z,u,v,w,arr[maxn],fa[maxn],vis[maxn],dis[maxn],sta[maxn];
vector<pair<int,int> >e[maxn];
int getfa(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=getfa(fa[x]);
}
void merge(int x,int y)
{
    if(x==y)return;
    fa[getfa(x)]=getfa(y);
    return;
}
void dfs(int u)
{
    for(auto v:e[u])
    {
        int x=v.first,y=v.second;
        if(!vis[x])
        {
            vis[x]=1;
            dis[x]=dis[u]+y;
            dfs(x);
        }
        else if(dis[x]!=dis[u]+y)sta[getfa(u)]=1;
    }
    return;
}
signed main()
{
//  freopen("path.in","r",stdin);
//  freopen("path.out","w",stdout);
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        sta[u]=(u==v and w>0);
        e[u].push_back({v,w});
        e[v].push_back({u,-w});
        merge(u,v);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[getfa(i)])dfs(i);
        vis[getfa(i)]=1;
    }
    while(t--)
    {
        cin>>u>>v;
        if(getfa(u)!=getfa(v))cout<<"nan\n";
        else if(sta[getfa(u)])cout<<"inf\n";
        else cout<<dis[v]-dis[u]<<"\n";
    }
    return 0;
}