TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4936
  • 题目
  • P4936飞行路线
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,128m
    问题描述

    Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务,设这些城市分别标记为0到n-1,一共有m种航线,每种航线连接两个城市,并且航线有一定的价格。
    Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。
    航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少?

    输入格式

    数据的第一行有三个整数,n,m,k,分别表示城市数,航线数和免费乘坐次数。

    第二行有两个整数,s,t,分别表示他们出行的起点城市编号和终点城市编号。(0<=s,t<n)

    接下来有m行,每行三个整数,a,b,c,表示存在一种航线,能从城市a到达城市b,或从城市b到达城市a,价格为c。(0<=a,b<n,a与b不相等,0<=c<=1000)

    输出格式

    只有一行,包含一个整数,为最少花费。

    样例输入 1

    5 6 1
    0 4
    0 1 5
    1 2 5
    2 3 5
    3 4 5
    2 3 3
    0 2 100

    样例输出 1

    8

    样例输入 2

    5 8 0
    1 0
    0 3 165
    0 4 104
    4 0 139
    1 2 326
    3 1 874
    2 0 678
    4 2 308
    4 2 594

    样例输出 2

    738

    提示

    对于30%的数据,2<=n<=50,1<=m<=300,k=0;

    对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1;

    对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10.


    来源  bzoj 2763 jloi2011