TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2784
  • 题目
  • P2784【APIO2013】道路费用
    限制 : 时间限制 : 50000 MS   空间限制 : 165536 KB
    问题描述

    时限2.5s

    输入格式

    你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数N,M和K。接下来的 M行描述最开始的M 条道路。这M行中的第i行包含由空格隔开的整数ai,bi和c i,表示有一条在a i和b i之间,费用为c i的双向道路。接下来的K行描述新建的K条道路。这 K行中的第i行包含由空格隔开的整数 xi和yi,表示有一条连接城镇xi和yi新道路。最后一行包含N个由空格隔开的整数,其中的第j个为pj,表示从城镇j 前往城镇 1的人数。
    输入也满足以下约束条件。

      1 ≤ N ≤ 100000;
      1 ≤ K ≤ 20;

      1 ≤ M ≤ 300000;

      对每个i和j,1 ≤ ci, pj ≤ 10^6;

    输出格式

    你的程序必须输出恰好一个整数到标准输出,表示能获得的最大的收入。

    样例输入 1

    5 5 1
    3 5 2
    1 2 3
    2 3 5
    2 4 4
    4 3 6
    1 3
    10 20 30 40 50

    样例输出 1

    400

    样例输入 2

    10 20 1
    1 2 820
    2 3 1340
    3 4 2680
    4 5 2000
    5 6 3380
    6 7 2480
    7 8 1560
    8 9 3160
    9 10 3240
    6 2 27
    6 3 54
    7 2 58
    9 6 105
    3 8 204
    4 2 326
    5 2 437
    4 9 584
    5 3 741
    8 10 864
    2 10 1042
    1 3
    483455 981707 922153 240078 591518 692941 155286 878466 230983 25611

    样例输出 2

    3869369260

    提示

     

    在样例中, Mr. Greedy应该将新道路(1,3)的费用设置为 5分钱。在这个费用下,他可以选择道路(3,5),(1,2),(2,4)和(1,3)来最小化总费用,这个费用为   14。从城镇 3出发的 30个人和从城镇 5出发的 50个人将经过新道路前往城镇 1,因此他可以获得为(30+50)_5=400 分钱的最好收入。

    如果我们这样做,将新道路(1,3)的费用设置为 10分钱。根据传统的限制,Mr. Greedy必须选择(3,5),(1,2),(2,4)和(2,3),因为这是唯一费用最小的集合。因此,在嘉年华的过程中道路(1,3)将没有任何收入。