頂点 \(A_i\) から頂点 \(B_i\) へコスト \(-C_i\) の有向辺、頂点 \(B_i\) から頂点 \(A_i\) へコスト \(C_i\) の有向辺があるときの、頂点 \(X\) から頂点 \(Y\) への最小コストの \(-1\) 倍が求めるものです。

\(X,Y\) が同じ連結成分に属していないとき答えは nan です。連結成分ごとに考えればよいため、以下ではグラフは連結であるとします。

頂点 \(V\) を任意に固定し、\(V\) を起点に各頂点へのコストを求めます。
ここで、\(V\) からのコストが一意でない頂点が存在することと、コストが \(0\) でない close walk が存在することが同値になります。

コストが \(0\) でない close walk が存在するとき、これをどちらかの方向に回ればいくらでもコストを下げられるのでどの2点間に対する答えも inf となります。

そうでないとき、任意の close walk のコストは \(0\) です。\(d(x,y)\) を 頂点 \(x\) から頂点 \(y\) への最小コストとすると、任意の \(x,y\) について
\(d(x,y)+d(y,x)=0\) と \(d(x,y)+d(y,V)+d(V,x)=0\) より \(d(x,y)=d(V,y)-d(V,x)\) となります。\(V\) から各頂点までのコストは一意であったことから、各 \(d(V,x)\) はBFS/DFS で求めることができます。

以上より、\(O(N+M)\) の前計算の下、各クエリは \(O(1)\) 時間で答えられます。

writer解(C++)
※この実装では DSU を使用しているため、前計算 \(O(N+M\alpha(N))\) クエリあたり \(O(\alpha(N))\) です。