| 比赛场次 | 331 |
|---|---|
| 比赛名称 | 防止颓废的小练习v0.3 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2016-10-19 09:30:00 |
| 结束时间 | 2016-10-19 18:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 |
| 题目名称 | 道路重建 |
|---|---|
| 输入输出 | rebuild.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试点数 | 9 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 农场主 |
AAAAAAAAA | 0.028 s | 1.00 MiB | 100 |
 ciyou |
0.000 s | 0.00 MiB | 0 |
【问题描述】
有一次，在一个王国中，有N个城市。N条道路可以让你从一个城市到其他任何一个城市。在两个城市之间最多有1条道路，但在一次严酷的战争后，有D条路被破坏。国王想要修理这些路，A和B是两个重要的城市，国王想要让两个城市尽快的连接，现在你的工作就是重建道路使A和B连接且重建道路的总长度最少。
【输入格式】
输入文件第一行包括一个整数$N（2<N≤100）$表明城市数。这些城市编号为从1到N。第二行包括一个整数$M(N-1≤M≤\frac {N(N-1)}{2})$，表明道路的数量。下面有M行，每行有3个整数$I,J,K(1<=I,J<=N,I!=J,0<K<=100)$.
意思是城市I与城市J之间道路的长度为K。
下一行包括一个整数$D(1≤D≤M)$，表示有几条路被破坏。下面D行包括2个整数$I,J,$表示城市I与城市J之间的道路被破坏且可以直接连接。
最后一行有两个整数A和B，表示两个重要的城市。
【输出格式】
对于每组测试数据，输出只有一行是可以使A和B连接的重建道路的总长度。
【输入样例】
输入文件名：rebuild.in
3
2
1 2 1
2 3 2
1
1 2
1 3
2
1 2 1
2 3 2
1
1 2
1 3
输出文件名：rebuild.out
1