問題一覧 > 通常問題

No.1600 Many Shortest Path Problems

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : e869120 / テスター : ngtkana 👑 ygussany
8 ProblemId : 6422 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-08 23:26:19

問題文

N 頂点 M 辺の重み付き無向グラフが与えられます。
辺には 1,2,…,M と番号が付けられており、辺 i は頂点 Ai と Bi を双方向に結ぶ、長さ 2i の辺です。

Q 個の質問に答えてください。i (1≤i≤Q) 個目の質問は、次のような形式です。

  • 整数 xi,yi,zi が与えられる。
  • 頂点 xi から頂点 yi に向かう辺 zi を通らないパスの中で、長さが最小のものにおける、パスの長さを 109+7 で割った余りを求めよ。

入力

N M
A1 B1
A2 B2
A3 B3
 ⋮
AM BM
Q
x1 y1 z1
x2 y2 z2
x3 y3 z3
 ⋮
xQ yQ zQ

出力

Q 行にわたって出力してください。
i 行目には、i 個目の質問の答えを出力してください。ただし、「頂点 xi から頂点 yi に向かう、辺 zi を通らないパス」が存在しない場合は、その行について −1 と出力してください。

制約

  • 2≤N≤200000
  • 1≤M≤200000
  • 1≤Ai<Bi≤N
  • (Ai,Bi)≠(Aj,Bj) [i≠j]
  • 1≤Q≤200000
  • 1≤xi<yi≤N
  • 1≤zi≤M
  • どの頂点からどの頂点へも、いくつかの辺を通ってたどり着くことができる
  • 入力はすべて整数

サンプル

サンプル1
入力
3 3
1 2
2 3
1 3
3
1 2 1
2 3 1
1 3 1
出力
12
4
8

各質問に対する答えは、次のようになります。

  • 1 個目の質問：頂点 1 から 2 へ向かう、辺 1 を含まないパスを考える。パス「1→3→2」は長さ (22+23)=12 であり、これが最短である。
  • 2 個目の質問：頂点 2 から 3 へ向かう、辺 1 を含まないパスを考える。パス「2→3」は長さ 22=4 であり、これが最短である。
  • 3 個目の質問：頂点 1 から 3 へ向かう、辺 1 を含まないパスを考える。パス「1→3」は長さ 23=8 であり、これが最短である。

サンプル2
入力
5 4
1 2
2 3
2 4
3 5
3
1 5 1
1 5 3
2 4 1
出力
-1
22
8

頂点 xi から yi までのパスのうち、辺 zi を通らないものが存在しない場合、−1 と出力してください。

サンプル3
入力
10 20
1 9
5 9
7 10
4 6
8 9
5 10
3 8
1 6
6 7
3 9
7 9
3 4
5 6
1 7
2 6
6 8
2 5
4 5
3 7
4 10
10
5 6 6
3 10 2
5 8 17
6 9 19
7 8 17
7 9 16
7 10 9
8 10 7
4 10 8
1 4 13
出力
262
938
36
258
108
76
8
100
536
272

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。