問題一覧 > 通常問題

No.1600 Many Shortest Path Problems

レベル : / AI推定難易度 : 2225 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 21
作問者 : e869120 / テスター : ngtkana ygussany
お気に入りにしたユーザー ProblemId : 6422 / 自分の提出
問題文最終更新日: 2021-07-08 23:26:19
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
競プロ典型 90 問 期末試験 (順位表) の他の問題:

Problem Statement

You are given a weighted undirected graph with $N$ vertices and $M$ edges.
The edges are numbered $1, 2, \dots, M$, and edge $i$ bidirectionally connects vertices $A_i$ and $B_i$ and has length $2^{i}$.

Answer $Q$ queries. The $i$-th $(1 \leq i \leq Q)$ query has the following form.

  • You are given integers $x_i, y_i, z_i$.
  • Among the paths from vertex $x_i$ to vertex $y_i$ that do not use edge $z_i$, consider one with the minimum length, and find the length of that path modulo $10^9 + 7$.

Input

$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$

Output

Output $Q$ lines.
On the $i$-th line, output the answer to the $i$-th query. However, if there is no "path from vertex $x_i$ to vertex $y_i$ that does not use edge $z_i$", output $-1$ on that line.

Constraints

  • $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$
  • Every vertex can be reached from every other vertex by traversing some edges.
  • All input values are integers.

Sample

Sample 1
Input
3 3
1 2
2 3
1 3
3
1 2 1
2 3 1
1 3 1
Output
12
4
8

The answers to the queries are as follows.

  • Query $1$: Consider the paths from vertex $1$ to $2$ that do not contain edge $1$. The path "$1 \to 3 \to 2$" has length $(2^2 + 2^3) = 12$, and this is the shortest.
  • Query $2$: Consider the paths from vertex $2$ to $3$ that do not contain edge $1$. The path "$2 \to 3$" has length $2^2 = 4$, and this is the shortest.
  • Query $3$: Consider the paths from vertex $1$ to $3$ that do not contain edge $1$. The path "$1 \to 3$" has length $2^3 = 8$, and this is the shortest.

Sample 2
Input
5 4
1 2
2 3
2 4
3 5
3
1 5 1
1 5 3
2 4 1
Output
-1
22
8

If there is no path from vertex $x_i$ to $y_i$ that does not use edge $z_i$, output $-1$.

Sample 3
Input
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
Output
262
938
36
258
108
76
8
100
536
272

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