Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Need for Seed

By ishtupeed · Limits 1s, 512 MB

The Need for Seed is a racing video game set in the fictional Fortune City. You, as a player of the game, need to carry seeds to the farmers by driving your car from one town to another. There are NN towns in Fortune City conveniently numbered from 00 to N1N-1. The towns are connected by MM weighted bidirectional roads. Each town has a unique positive integer difficulty level, diffdiff. The time taken to go from one town to another can be different. When you drive from town uu to town vv, you will face obstacles if diff[u]<diff[v]diff[u] < diff[v]. The weight of each road denotes the time taken to go from one town to another.

There will be multiple races in the game. In each race, you will start from town XiX_i and your goal is to reach town YiY_i. Assume that whenever your car hits an obstacle, you lose all the seeds. So your goal is to reach town YiY_i without facing any obstacles. You also want to minimize the time taken to go from town XiX_i to town YiY_i.

You need to determine the minimum time required to go from town XiX_i to town YiY_i.

Input

Input will start with an integer TT, denoting the number of test cases.

Each test case will start with 3 space-separated integers NN, MM, and LL, where NN denotes the number of towns in Fortune City, MM denotes the number of roads connecting them, and LL denotes the number of races to be held.

The following line will contain NN space-separated integers diff[0],diff[1],,diff[N1]diff[0], diff[1], \dots, diff[N-1] where diff[i]diff[i] denotes the difficulty of the ithi^{th} town.

The next MM lines each will contain 3 space-separated integers uu, vv, and ww indicating that there’s a bidirectional road between the town uu and town vv with that takes timeww.

The following LL lines each will contain two space-separated integers XiX_i and YiY_i, where XiX_i denotes the starting town and YiY_i denotes the goal town for the ithi^{\text{th}} race.

Constraints

  • 1N1051 \leq N \leq 10^5

  • 1M1051 \leq M \leq 10^5

  • 1L1001 \leq L \leq 100

  • 1diff[i]1091 \leq diff[i] \leq 10^9 where 0i<N0 \leq i < N

  • 0u,v<N0 \leq u, v < N

  • 1w1091 \leq w \leq 10^9

  • 0Xi,Yi<N0 \leq X_i, Y_i < N where 0i<L0 \leq i < L

  • 1T51 \leq T \leq 5

Subtask #1 (40 points): 1L201 \leq L \leq 20

Subtask #2 (60 points): Original constraints

Output

For each race, if there exists no path from town XiX_i to town YiY_i, print 1-1. Otherwise, print the time taken to reach YiY_i. Print a newline after the output of each race.

Sample

InputOutput
1
3 3 2
3 2 1
0 1 1
0 2 3
1 2 1
0 2
2 0
2
-1

    Discussion

    Statistics


    58% Solution Ratio

    jamil314Earliest, 4M ago

    Ahasan_1999Fastest, 0.2s

    sakib.17442Lightest, 6.9 MB

    Deshi_TouristShortest, 982B

    Submit

    Login to submit

    Editorial

    Construct a weighted directed graph on the NNN towns, with a directed edge from town uuu to town vvv...

    Toph uses cookies. By continuing you agree to our Cookie Policy.