F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

path

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4331    Accepted Submission(s): 1013


Problem Description
You have a directed weighted graph with $n$ vertexes and $m$ edges. The value of a path is the sum of the weight of the edges you passed. Note that you can pass any edge any times and every time you pass it you will gain the weight.

Now there are $q$ queries that you need to answer. Each of the queries is about the k-th minimum value of all the paths.
 

Input
The input consists of multiple test cases, starting with an integer $t$ $(1\leq t\leq 100)$, denoting the number of the test cases.
The first line of each test case contains three positive integers n,m,q. $(1\leq n,m,q\leq 5*10^4)$

Each of the next $m$ lines contains three integers $u_i,v_i,w_i$, indicating that the $i-th$ edge is from $u_i$ to $v_i$ and weighted $w_i$.$(1\leq u_i,v_i \leq n,1\leq w_i\leq 10^9)$

Each of the next $q$ lines contains one integer $k$ as mentioned above.$(1\leq k\leq 5*10^4)$

It's guaranteed that $\Sigma n$ ,$\Sigma m$, $\Sigma q , \Sigma \max(k)\leq 2.5*10^5$ and $\max(k)$ won't exceed the number of paths in the graph.
 

Output
For each query, print one integer indicates the answer in line.
 

Sample Input
1 2 2 2 1 2 1 2 1 2 3 4
 

Sample Output
3 3
 

Hint

1->2 value :1

2->1 value: 2

1-> 2-> 1 value: 3

2-> 1-> 2 value: 3

 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 06:50:30, Gzip enabled