D - Shortest Paths on Unicyclic Graph

2 secs 1024 MB
magurofly's icon magurofly

問題文

NN 頂点 NN 辺の単純かつ連結な無向グラフが与えられます。 このグラフの ii 番目の辺は頂点 AiA_i と頂点 BiB_i を相互に結び、長さは CiC_i です。

このグラフ上の最短路クエリが QQ 個与えられるので、これに答えてください。 jj 番目のクエリでは頂点 XjX_j と頂点 YjY_j の間の最短路を求めてください。

制約

  • 3N2×1053 \le N \le 2\times 10^5
  • 1Ai,BiN1 \le A_i, B_i \le N
  • 1Ci10121 \le C_i \le 10^{12}
  • 1Q2×1051 \le Q \le 2\times 10^5
  • 1Xj,YjN1 \le X_j, Y_j \le N
  • 入力はすべて整数である

入力

N QA1 B1 C1A2 B2 C2AN BN CNX1 Y1X2 Y2XQ YQN\ Q\\ A_1\ B_1\ C_1\\ A_2\ B_2\ C_2\\ \vdots\\ A_N\ B_N\ C_N\\ X_1\ Y_1\\ X_2\ Y_2\\ \vdots\\ X_Q\ Y_Q

出力

QQ 行出力してください。 j=1,2,,Qj = 1, 2, \ldots, Q について、 jj 行目には jj 番目のクエリに対する答えを出力してください。

入出力例

入力例1
4 3
1 2 1
1 3 2
3 4 4
4 1 8
1 2
1 4
4 2
出力例1
1
6
7
入力例2
11 6
1 5 1
7 5 2
1 7 4
2 1 8
2 4 16
3 2 32
5 6 64
8 7 128
9 7 256
9 10 512
11 9 1024
1 7
3 6
11 8
11 10
4 10
6 9
出力例2
3
105
1408
1536
795
322
入力例3
10 10
10 7 508252356070
10 4 328974562802
9 1 885368849936
9 10 580933898755
9 5 349344869736
1 6 394235217277
10 3 21578149681
1 2 19279158318
6 4 803839369377
9 8 982198770298
1 6
8 2
1 4
1 7
7 6
6 10
5 7
4 3
10 2
4 8
出力例3
394235217277
1886846778552
1198074586654
1974555104761
1641066288249
1132813932179
1438531124561
350552712483
1485581907009
1892107231855

提出


Go (1.21)