問題一覧 > 通常問題

No.1600 Many Shortest Path Problems

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

問題文

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

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

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

入力

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$A_3$ $B_3$
 $\vdots$
$A_M$ $B_M$
$Q$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$x_3$ $y_3$ $z_3$
 $\vdots$
$x_Q$ $y_Q$ $z_Q$

出力

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

制約

  • $2 \leq N \leq 200000$
  • $1 \leq M \leq 200000$
  • $1 \leq A_i < B_i \leq N$
  • $(A_i, B_i) \neq (A_j, B_j)$ $[i \neq j]$
  • $1 \leq Q \leq 200000$
  • $1 \leq x_i < y_i \leq N$
  • $1 \leq z_i \leq 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 \to 3 \to 2$」は長さ $(2^2 + 2^3) = 12$ であり、これが最短である。
  • $2$ 個目の質問:頂点 $2$ から $3$ へ向かう、辺 $1$ を含まないパスを考える。パス「$2 \to 3$」は長さ $2^2 = 4$ であり、これが最短である。
  • $3$ 個目の質問:頂点 $1$ から $3$ へ向かう、辺 $1$ を含まないパスを考える。パス「$1 \to 3$」は長さ $2^3 = 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

頂点 $x_i$ から $y_i$ までのパスのうち、辺 $z_i$ を通らないものが存在しない場合、$-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もしくは右上の雲マークをクリックしてアカウントを作成してください。