• [1483] 嘛~寝室寝室!

  • 时间限制: 2000 ms 内存限制: 65535 K
  • 问题描述
  • 啦啦啦~集训终于开始了(虽然你们看到这道题目的时候集训已经要结束了)!!但是由于东西校区的缘故,在东校区的孩子不得不跑到西校区来,于是如何分配寝室就成了一个问题。由于集训的人数多,寝室提供的数量又不多,于是我们必须赶在其它“XXX”孩子住进去之前先住进去。
  • 输入
  • 第一行输如N(1<=N<=300),M(1<=M<=1500)。分别代表学校提供了N个寝室楼,M条路径连接寝室楼。
    接下来有N行,每行两个数A(1<= A <= 1000),B(1 <= B <= 1000)。分别代表第i个寝室楼(第i行)里,已经在了A个同学,这栋寝室楼里只提供B个寝室。
    在接下来M行,每行三个数x,y,z(1<= z <= 1,000,000,000)。表示从第x栋楼去第y栋楼所需z分钟,当然从y到x也需要z分钟。
    输入到文件尾结束。
  • 输出
  • 输出所有集训队的孩子分配好住的地方需要最短的时间。如果不能分配到寝室,输出-1。
  • 样例输入
  • 4 6
    8 3
    4 5
    0 9
    3 4
    1 3 120
    2 4 10
    1 2 70
    2 3 20
    2 1 50
    3 4 90
    4 6
    9 3
    4 5
    0 9
    3 4
    1 3 120
    2 4 10
    1 2 70
    2 3 20
    2 1 50
    3 4 90
  • 样例输出
  • 50
    60
  • 提示
  • 来源
  • Minary
  • 操作

显示春菜