TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3763
  • 题目
  • P3763修公路
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 时限1000ms
    问题描述

    某岛国有n个小岛构成(编号1到n),该国政府想要通过n-1条双向公路将这些小岛连接起来,使得任意两个岛屿之间都能相互到达。公路有两种,一种是高速公路,车速快,建设花费大;另一种是普通公路,车速慢,建设花费少。该国政府不想在一条公路上花费过多的钱,但又要求修建的公路中至少有k条高速公路。所以政府希望,在满足上述条件的情况下,使得最贵的一条公路花费尽可能少,请你帮忙计算出其中最贵一条公路的价格。

    输入格式

    第一行,三空格间隔的整数n,k,m,其中m表示有m对岛屿间可以修路。
         接下来以下的m行,每行四个正整数a,b,c1,c2 表示在岛屿a与b 之间修高速公路花费c1块钱,修普通公路,花费c2块钱。

    输出格式

    一个整数表示最贵那条公路的费用。

    样例输入 1

    4 2 5
    1 2 6 5
    1 3 3 1
    2 4 6 1
    3 4 4 2

    样例输出 1

    4

    样例输入 2

    4 1 5
    1 2 6 5
    1 3 3 1
    2 3 9 4
    2 4 6 1
    3 4 4 3

    样例输出 2

    3

    样例输入 3

    10 4 19
    3 9 6 3
    1 3 4 1
    5 3 10 2
    8 9 8 7
    6 8 8 3
    7 1 3 2
    4 9 9 5
    10 8 9 1
    2 6 9 1
    6 7 9 8
    2 6 2 1
    3 8 9 5
    3 2 9 6
    1 6 10 3
    5 6 3 1
    2 7 6 1
    7 8 6 2
    10 9 2 1
    7 1 10 2

    样例输出 3

    5

    提示

    对于30%的数据, 1<=n<=1000           0<=k<=10             n-1<=m<=3000

    对于100%的数据,1<=n<=10000          0<=k<=n-1            n-1<=m<=20000


    来源  hnoi2006