No.1600 Many Shortest Path Problems
問題文最終更新日: 2021-07-08 23:26:19
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
e869120
ngtkana