? - MarisaOJ: Marisa Online Judge

Given a weighted undirected graph with

n

$n$ vertices and

m

$m$ edges. For each vertex

i

$i$ , you can pass through this vertex from time

t_{i}

$t_i$ onwards. Given

q

$q$ queries of the form

(x, y, t)

$(x, y, t)$ , find the shortest path from

x

$x$ to

y

$y$ at time

t

$t$ . ### Input - The first line contains two integers

n, m

$n, m$ . - The second line contains

n

$n$ integers

t_{i}

$t_i$ . Ensure

0 \leq t_{1} \leq t_{2} \leq \dots \leq t_{n} \leq 1000

$0 \le t_1 \le t_2 \le \ldots \le t_n \le 1000$ . - The next

m

$m$ lines each contain three integers

u, v, w

$u, v, w$ . Ensure there is at most one edge between any two vertices. - The next line contains an integer

q

$q$ . - The next

q

$q$ lines each contain three integers

(x, y, t)

$(x, y, t)$ . ### Output - For each query, print an integer representing the length of the shortest path, or print

- 1

$-1$ if no path exists. ### Constraints -

1 \leq n \leq 500

$1 \le n \le 500$ . -

1 \leq m \leq \frac{n \times (n - 1)}{2}

$1 \le m \le \frac{n \times (n - 1)}{2}$ . -

1 \leq u \neq v \leq n

$1 \le u \neq v \le n$ . -

1 \leq w \leq 10^{4}

$1 \le w \le 10^4$ . -

1 \leq q \leq 5 \times 10^{4}

$1 \le q \le 5 \times 10^4$ . -

1 \leq x \neq y \leq n

$1 \le x \neq y \le n$ . -

0 \leq t \leq 1000

$0 \le t \le 1000$ . ### Example Input:

4512341313414223241454312122123124

$4 5 1 2 3 4 1 3 1 3 4 1 4 2 2 3 2 4 1 4 5 4 3 1 2 1 2 2 1 2 3 1 2 4$

Output:

- 1 - 154

$-1 -1 5 4$

Topic

Graph

Shortest path

Rating

1600

Source

Luogu

Solution (0)

Solution