编程介的小学生 2019-08-27 18:11 采纳率: 20.5%
浏览 81

Island and study-sister程序编制的思路

Problem Description
Members of ACM/ICPC teams of Fuzhou University always stay in the laboratory in their free time. One day the team members of OOXX are doing their daily training and suddenly received k calls from study-sisters asking for their help. You can regard the campus of Fuzhou University is consist of n beautiful islands and connected by m undirection bridges and the study-sisters are in some of these islands waiting for them. As the members of OOXX are all warm-hearted, they don’t want these study-sisters waiting too long and just want the time the girl whom waiting for the longest be as short as possible. You can assume that they begin to move immediately after they received the calls. They start from the laboratory and they can go anywhere freely by the bridges.
But due to some mysterious reason, each island can be visited only by one member except the laboratory. This means that even if two guys come to an island in two different times is forbidden. Now your task is calculating how long these study-sisters will wait. Note that there are three students in team OOXX.

Input
The first line contains only one integer T (T<=150), which is the number of test cases. Each test case contains two integer n (1<= n <=17), m (m <= n*n), means that Fuzhou university is consist of n islands and there are m undirection bridges connect them. Then comes m lines, each line contains three integer x, y, s, means that there is a bridge connect island x and island y and it takes s unit of time to go through this bridge. The numbers start from 1 to n and the number of the laboratory is always 1. Then comes a number k (k>=1) indicate that there are k study-sisters waiting for help. The next line are k integers xi (2<=xi<=n) describe where these study-sisters are. You can assume that all the study-sisters are in different islands.

Output
For each test case, output the case number first, then output the time the girl whom wait for the longest wait. You should make this number as small as possible. If any one of the study-sisters can’t get help, just output -1.

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

Sample Output
Case 1: -1
Case 2: 1
Case 3: 7
Case 4: 4

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 本题的答案是不是有问题
    • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
    • ¥15 C++使用Gunplot
    • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
    • ¥15 matlab数字图像处理频率域滤波
    • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
    • ¥15 ELGamal和paillier计算效率谁快?
    • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
    • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
    • ¥15 Arcgis相交分析无法绘制一个或多个图形