编程介的小学生 2017-03-29 15:45 采纳率: 20.5%
浏览 715
已采纳

Gao

Who is cpcs? Every one in ZJU ACM-ICPC team knows him. Although he has been graduated from ZJU, he is still active in ZOJ and many contests. cpcs is the legendary figure in ZJU ACM-ICPC history. It is not only because he has passed nearly all the problems on ZOJ, but also because his very famous function name "gao" which is now widely spreaded and used by many ACMers.

"gao" in Chinese means to do something but it's not that formal in grammar. So it is usually used verbally. In addition, "gao" can be explained as a spirit, a belief, even an attitude to life, which makes cpcs use "gao" as most of the function names (Of course there should be some functions named such as "main" in C or C++).

One day, cpcs got a map of the city he lived in. There were N buildings (numbered from 0 to N - 1) in the map with the building he was in marked as 0. Between the buildings, there were some unidirectional roads. He then wrote a program with function "gao" that could calculate all the shortest paths from building 0 to all the building. Here, there might be more than one shortest paths to a building. Now he wanted to know, for each query of buildings, how many shortest paths that he figured out with function "gao" passed through the queried building. Note that if a building is unreachable from building 0, no shortest path would passes through it.

Input

There are multiple test cases. For each case, the first line is three numbers N, M, Q (1 ≤ Q ≤ N ≤ 10000, 1 ≤ M ≤ 50000) indicating the number of buildings, the number of roads and the number of queries. Next is M lines each containing three numbers a, b, d (0 ≤ a, b < N, 0 < d ≤ 200) indicating that there is a road of length d from building a to building b. Next is Q lines each containing one integer qi indicating a query to a building. Most cases are small, no more than 5 large cases.

Output

In each case, for each query, you should print one line with the number of shortest paths that pass through the building. Since the answer may be very large, you only need to print the last 10 digits of the answer.

Sample Input

4 4 4
0 1 2
0 2 2
1 3 1
2 3 1
0
1
2
3
Sample Output

0000000005
0000000002
0000000002
0000000002
Hint

In the sample, there are 5 shortest paths.

0
0 -> 1
0 -> 2
0 -> 1 -> 3
0 -> 2 -> 3
Therefore, building 0 appears 5 times in the shortest paths, while building 1, 2 and 3 each appears 2, 2, 2 times.

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-04-07 14:57
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题