跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0176. #2110. 「JLOI2015」管道连接

  • ID: 182
  • 传统题
  • 1000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#2110. 「JLOI2015」管道连接

题目描述

小铭铭最近进入了某情报部门,该部门正在被如何建立安全的通道连接困扰。

该部门有 个情报站,用 到 的整数编号。给出 对情报站 和费用 ,表示情报站 和 之间可以花费 单位资源建立通道。

如果一个情报站经过若干个建立好的通道可以到达另外一个情报站,那么这两个情报站就建立了通道连接。形式化地,若 和 建立了通道,那么它们建立了通道连接;若 和 均与 建立了通道连接,那么 和 也建立了通道连接。现在在所有的情报站中,有 个重要情报站,其中每个情报站有一个特定的频道。

小铭铭面临的问题是,需要花费最少的资源,使得任意相同频道的情报站之间都建立通道连接。

输入格式

第一行包含三个整数 ,表示情报站的数量,可以建立的通道数量和重要情报站的数量。

接下来 行,每行包含三个整数 ,表示可以建立的通道。最后有 行,每行包含两个整数 ,表示重要情报站的频道和情报站的编号。

输出格式

输出一行一个整数,表示任意相同频道的情报站之间都建立通道连接所花费的最少资源总量。

样例

样例输入

5 8 4
1 2 3
1 3 2 
1 5 1
2 4 2
2 5 1
3 4 3 
3 5 1
4 5 1
1 1
1 2
2 3
2 4

样例输出

4

样例解释

选择 这四对情报站连接。

数据范围与提示

对于 的数据,。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 60 题。保留原作者与原赛事署名。