hdu 6166 Senior Pan(随机+最短路)

Problem Description
Senior Pan fails in his discrete math exam again. So he asks Master ZKC to give him graph theory problems everyday.
The task is simple : ZKC will give Pan a directed graph every time, and selects some nodes from that graph, you can calculate the minimum distance of every pair of nodes chosen in these nodes and now ZKC only cares about the minimum among them. That is still too hard for poor Pan, so he asks you for help.

 

Input
The first line contains one integer T, represents the number of Test Cases.1≤T≤5.Then T Test Cases, for each Test Cases, the first line contains two integers n,m representing the number of nodes and the number of edges.1≤n,m≤100000
Then m lines follow. Each line contains three integers xi,yi representing an edge, and vi representing its length.1≤xi,yi≤n,1≤vi≤100000
Then one line contains one integer K, the number of nodes that Master Dong selects out.1≤K≤n
The following line contains K unique integers ai, the nodes that Master Dong selects out.1≤ai≤n,ai!=aj

 

Output
For every Test Case, output one integer: the answer

 

Sample Input
1
5 6
1 2 1
2 3 3
3 1 3
2 5 1
2 4 2
4 3 1
3
1 3 5

 

Sample Output
Case #1: 2
因为我们要考虑的是集合内的最短路,相当于是个多源多汇的最短路。有一种非常神奇的随机的方式,就是把集合等分为两个集合,分别视为起点集合和终点集合。然后建个超级源汇跑dij就可以了,当然这样有1/4的概率跑出来正确答案,所以随机20次就可以了。
讲课的时候口胡了一下,现在写了写。。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注