Another Contest 2 Problem 1 - Poutine

View as PDF

Submit solution


Points: 15
Time limit: 0.6s
Memory limit: 256M

Problem types

Fast Fingers Thomas is delivering poutine to Wilson's restaurants!

Fast Fingers Thomas will drive a truck on a directed, weighted graph with N vertices. The weight of each edge in the graph is the length of the edge. He has Q trips he needs to make.

Each trip has three parameters, a source vertex s_i, a destination vertex t_i, and a number of days d_i. Thomas has d_i days to travel from vertex s_i to vertex t_i. In a given day, Thomas starts at a vertex and traverses a nonnegative number of edges, ending the day at some vertex (possibly the same one). Define f(s_i, t_i, d_i) to be the smallest value such that, in a single day, the sum of the weights of the edges that Thomas drives on does not exceed f(s_i, t_i, d_i), and subject to this, Thomas can get from s_i to t_i in d_i days. In the event that it's impossible to do this, Thomas does no driving and f(s_i, t_i, d_i) is zero.

Constraints

2 \le N \le 100

1 \le Q \le 10^5

0 \le w_{ij} \le 10^9

1 \le s_i, t_i \le N

s_i \ne t_i

1 \le d_i < N

All queries are pairwise distinct.

Input Specification

The first line contains a single positive integer, N.

The next N lines contain N space-separated non-negative integers. The jth integer in the ith line of this section, w_{ij}, indicates the length of the directed edge connecting vertex i to vertex j, or 0 if no such edge exists. It is guaranteed there are no self-loops.

The next line contains a single positive integer, Q.

The next Q lines each contain three space-separated positive integers, s_i, t_i, and d_i, representing a query for f(s_i, t_i, d_i).

Output Specification

Output Q lines. On the ith line, output the answer to the ith query.

Sample Input

3
0 1 2
1 0 1
2 1 0
2
1 3 1
1 3 2

Sample Output

2
1

Comments

There are no comments at the moment.