AC. 梦想

frank_c1

[BZOJ 2763] 飞行路线

发布于2016年01月17日 | 暂无评论 | 549阅读 | 最短路径

题目描述

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)

输出格式

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

题目解析

这道题感觉和不久前TC中一道题类似,都是最短路变式。题意是求无向图给定两点间在可将路径上任意K条边权值置为0时的最短路径。与一般最短路类似,令dp[i][j]表示到达i点时还有j次边权置0机会的最小花费,初始时dp[s][k] = 0,其余置为正无穷,然后随Dijkstra或SPFA转移即可,最终答案为\max \{ dp[t][i] \; | \; 0 \le i \le k\}