问题2040--小机关城

2040: 小机关城

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

天明最近对机关城起了兴趣。  他用一些小物件搭起了一座机关城，当然，这只能算是玩具。  现在，他有n个机关，从1到n编号，他现在想让一些机关联通。
由于一些特殊原因，只有m对机关才可能建立联系。  他打算用绳子连接两个机关表示这两个机关能相互联系。  而连接一对机关所需要的绳子长度可能不同。
他笨手笨脚，所以为了防止绳子打结，  他希望使用的绳子中最长的绳子长度最短。  不过，他又有t个计划，对于每个计划，都有一个参数x，  表示这个计划至少需要x个机关相连。  你要告诉他满足计划条件的最长绳子的最短长度。

输入

第一行n,m,t。
接下来m行，每行三个整数a,b,c，
表示a机关和b机关用长度为c的绳子可连接。
接下来一行，t个用空格分割的整数，表示t个计划的参数x，题目保证2<=x<=n。

输出

t行，每行一个整数，对应满足计划条件的最长绳子的最短长度，
如果不可能满足该计划，则输出QAQ。

样例输入 Copy 

5 5 2
1 2 228
4 2 194
5 4 1010
5 4 427
1 5 947
3 5

样例输出 Copy 

228
QAQ

提示

10<=n<=10000
10<=m<=10000
1<=t<=10
1<=a<=n
1<=b<=n
1<=c<=1024
2<=x<=n
题解：https://www.luogu.org/blog/qsmoon/post-ti-xie-1031-xiao-ji-guan-cheng

来源/分类

基础算法 
[提交] [状态]