← 返回题目列表

AtCoder · joi2014yo_e

E. 出租车

中文机器翻译题面 查看原题

配点: 100 点

問題

IOI 国有城镇 1 从城镇 N 最多 N 个城镇组成,城镇之间由道路连接。IOI 国有 K 条道路,所有道路都连接着不同的 2 个城镇。汽车可以在道路上双向自由行驶,但不能通过道路以外的地方从一个城镇前往另一个城镇。

IOI 国的城镇 1 居住在城镇的 JOI 君,决定乘出租车前往居住在城镇的祖母家。IOI 国有出租车公司 N 乘出租车前往祖母家。IOI 国有出租车公司 1 出租车公司 N 最多 N 个出租车公司。IOI 国的出租车公司有如下稍微特殊的规定。

  • 出租车公司 i 的出租车中,城镇 i 只能在……乘车。
  • 出租车公司 i 出租车的车费,无论乘坐的距离如何 C_i 都是……。
  • 出租车公司 i 出租车在乘车后连续最多 R_i 条道路。

例如 R_1 = 2 在……的情况下,如果在城镇 1 出租车公司 1 乘坐出租车,最多只能通行 2 条道路,因此为了通行至少 3 条道路,需要在中途的城镇换乘出租车。

打飞机君不能在城镇以外的地点乘坐出租车,也不能在城镇以外的地点下出租车。此外,也不能使用出租车以外的移动手段。请编写程序,求出 JOI 君到达城镇 N 所需车费总和的最小值。


入力

输入由 1 + N + K 行组成。

1 第 行中, 2 整数 N, K (2 \leqq N \leqq 5\,000,N - 1 \leqq K \leqq 10\,000) 以空格分隔给出。这表示 IOI 国由 N 个城镇组成,且 IOI 国的道路数为 K 条。

继续 N 在行中的 i 行目 (1 \leqq i \leqq N) 中,2 整数 C_i, R_i (1 \leqq C_i \leqq 10\,000,1 \leqq R_i \leqq N) 以空格分隔给出。这表示出租车公司 i 的出租车运费为 C_i ,最大 R_i 表示仅可使用主干道。

继续 K 在行中的 j 行目 (1 \leqq j \leqq K) 有不同 2 整数 A_j, B_j (1 \leqq Aj < Bj \leqq N)以空格作为分隔符。这是一个小镇 A_j 和镇 表示 B_j 之间有一条路。一样 集合 (A_j, B_j) 是 它从未被写入超过 2 次。

给定输入数据,保证您可以从任何城镇乘坐出租车到任何其他城镇。

出力

JOI 君美镇 一个整数,表示前往 1 从城镇 N 所需的最低总票价。 输出为 1 行。


入力例 1

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

出力例 1

700

上面的输入/输出示例对应于下图。圆圈代表城镇,线条代表道路。

在此输入/输出示例中,JOI 要到达 6 ,请执行以下操作。

町 1 乘出租车去镇上 转至 5 。 (票价 400)
町 5 乘出租车去镇上 转至 6 。 (票价 300)
JOI 如果您走这条路线,总票价为 400 + 300 = 700 ,所以 输出700 。