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

#F0291. #6209. 巡逻

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

#6209. 巡逻

题目描述

你作为一名市警察局局长,每天都要沿着城市的道路巡逻。这座城市共有 个地标,某些地标之间可能会有单向道路相连,这些道路共有 条,我们称这些单向道路为旧路。现在市里新修了 条单向道路,我们称这些单向道路为新路。每条旧路都有一个权值 ,表示通过这条道路消耗的油量;每条新路也有权值,也表示通过这条道路消耗的油量,不过权值是变化的。以第 条新路为例,一开始其权值为 ,若总共通过了 条新路,其权值就会变为 (在完全一条新路通过时才会改变)。不会存在两条旧路连接相同的两个地标,也不会存在两条新路连接相同的两个地标。
你的警察局位于城市的 号地标处,现在你需要通过恰好 条旧路和 条新路(都可以重复经过),并最终停在任意地标处。你希望知道完成这件任务最少需要消耗多少油。

输入格式

输入第一行为五个正整数 ,分别表示地标个数、旧路条数、需要经过的旧路条数、新路条数、需要经过的新路条数。
接下来 行,每行三个正整数 ,描述了一条从 指向 的旧路。
接下来 行,每行前两个正整数为 ,描述了一条从 指向 的新路。接下来 个正整数,分别为 ,表示与这条新路有关的权值。

输出格式

输出仅一行,一个正整数,表示最小的耗油量。如果无法完成任务,请输出 。

样例

样例输入

3 3 1 1 1
1 2 1
2 3 2
3 1 1
2 3 2

样例输出

3

数据范围与提示




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