Ray Needs Help

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Ray is planning something and needs your help. Ray needs your help to answer Q queries on a directed, weighted graph of N nodes and M edges.

For the i^{th} query he wants to compute the minimum weight of a walk from u_i to v_i that takes exactly k_i edges, and if no such walk exists, output -1 instead. A walk is similar to a path, but edges (and nodes) can be traversed multiple times. The weight of a walk is equal to the sum of weights of the edges it traverses, and if an edge is traversed multiple times, its weight will count multiple times towards the sum.

Constraints

1 \le N \le 100

1 \le M \le N^2

1 \le Q \le 2\,000

There may be duplicate edges and/or self-loops.

1 \le u_i, v_i, a_i, b_i \le N

1 \le w_i, k_i \le 10^9

Subtask 1 [25%]

Q = 1

k_i \le 100

Subtask 2 [35%]

Q = 1

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line contains the integers N, M, and Q.

The next M lines each contain the integers a_i, b_i, w_i, meaning that there is a directed edge from a_i to b_i with a weight of w_i. Note that it may be possible for a single pair of nodes to have multiple edges between them.

The next Q lines each contain a query in the form u_i, v_i, k_i.

Output Specification

For each query u_i, v_i, k_i, output the shortest walk from u_i to v_i that uses k_i edges. If no such walk exists, output -1 instead. The output of each query should be on a separate line.

Sample Input

5 7 7
2 1 1
1 2 3
1 4 10
4 5 1
3 4 1
2 3 4
3 5 5
2 4 2
2 4 6
2 4 7
2 5 3
3 5 1
3 5 2
3 5 3

Sample Output

5
13
-1
6
5
2
-1

Sample Explanation

Here are the answers to each query:

  • 2 4 2: 2 \rightarrow 3 \rightarrow 4
  • 2 4 6: 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4
  • 2 4 7: It can be shown that no such walk exists.
  • 2 5 3: 2 \rightarrow 3 \rightarrow 4 \rightarrow 5
  • 3 5 1: 3 \rightarrow 5
  • 3 5 2: 3 \rightarrow 4 \rightarrow 5
  • 3 5 3: It can be shown that no such walk exists.

Comments

There are no comments at the moment.