There are $N$ towns numbered $1,\ldots,N$ and $M$ roads numbered $1,\ldots,M$. Road $i$ connects towns $A_i$ and $B_i$. When you use a road, your score changes as follows: Your score may become negative. Answer the following $Q$ questions.Problem Statement
Here, if you cannot get from town $X_i$ to town $Y_i$, print nan instead; if you can have as large a score as you want when you are at town $Y_i$, print inf instead.Constraints
Input
The input is given from Standard Input in the following format:
$N$ $M$ $Q$ $A_1$ $B_1$ $C_1$ $\vdots$ $A_M$ $B_M$ $C_M$ $X_1$ $Y_1$ $\vdots$ $X_Q$ $Y_Q$
Output
Print $Q$ lines as specified in the Problem Statement.
The $i$-th line should contain the answer to the $i$-th question.
Sample Input 1
5 5 3 1 2 1 1 2 2 3 4 1 4 5 1 3 5 2 5 3 1 2 3 1
Sample Output 1
-2 inf nan
For the first question, if you use road $5$ to move from town $5$ to town $3$, you can have a score $-2$ when you are at town $3$.
Since you cannot make the score larger, the answer is $-2$.
For the second question, you can have as large a score as you want when you are at town $2$ if you travel as follows: repeatedly "use road $2$ to move from town $1$ to town $2$ and then use road $1$ to move from town $2$ to town $1$" as many times as you want, and finally use road $2$ to move from town $1$ to town $2$.
For the third question, you cannot get from town $3$ to town $1$.
Sample Input 2
2 1 1 1 1 1 1 1
Sample Output 2
inf
The endpoints of a road may be the same, and so may the endpoints given in a question.
Sample Input 3
9 7 5 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9
Sample Output 3
inf nan nan inf -9
nan 明显就是不同连通块的情况，而当且仅当一个连通块中存在的环都是0环，他这个连通块的点的答案才不是 inf。
但是怎么判断一个连通块是否存在非0环呢？其实可以从某一个点开始搜索，如果到达点 \(x\) 存在两条长度不相等的路径，那么就一定存在非0环。否则就无环或者只有0环。
那么现在已经确定了起始点到某个点的距离了，设起始点为 \(a\) 到点 \(x\) 距离为 \(dis_x\),点 \(x\) 到 点 \(y\) 的距离易得为 \(dis_y-dis_x\)。这是因为没有0环，所有 \(x\) 到 \(y\) 的路径都是同样距离，，当中存在一条路径为 \(x\rightarrow a\rightarrow y\)。
#include<bits/stdc++.h>
typedef long long LL;
const int N=1e5+5;
struct edge{
int v,nxt,w;
}e[N<<1];
int n,m,q,u,v,w,fa[N],hd[N],e_num,vs[N];
LL dp[N];
void add_edge(int u,int v,int w)
{
e[++e_num]=(edge){v,hd[u],w};
hd[u]=e_num;
}
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
void dfs(int x,LL w)
{
if(dp[x]==dp[0])
dp[x]=w;
else
{
if(dp[x]!=w)
vs[find(x)]=1;
return;
}
for(int i=hd[x];i;i=e[i].nxt)
dfs(e[i].v,w+e[i].w);
}
int main()
{
memset(dp,-0x7f,sizeof(dp));
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,-w);
fa[find(u)]=find(v);
}
for(int i=1;i<=n;i++)
if(fa[i]==i)
dfs(i,0);
while(q--)
{
scanf("%d%d",&u,&v);
if(find(u)!=find(v))
printf("nan\n");
else if(vs[find(u)])
printf("inf\n");
else
printf("%lld\n",dp[v]-dp[u]);
}
}