题目描述

Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 n 个城市设有业务，设这些城市分别标记为 0 到 n−1，一共有 m 种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 k 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

输入格式

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

接下来一行两个整数 s,t，分别表示他们出行的起点城市编号和终点城市编号。

接下来 m 行，每行三个整数 a,b,c，表示存在一种航线，能从城市 a 到达城市 b，或从城市 b 到达城市 a，价格为 c。

输出格式

输出一行一个整数，为最少花费。

输入输出样例

输入 #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

说明/提示

数据规模与约定

对于 30% 的数据，2≤n≤50，1≤m≤300，k=0。

对于 50% 的数据，2≤n≤600，1≤m≤6×103，0≤k≤1。

对于 100% 的数据，2≤n≤10^4，1≤m≤5×10^4，0≤k≤10，0≤s,t,a,b≤n，0≤c≤10^3。

另外存在一组 hack 数据。

题意： 给出一个n点m边的无向图以及起点s和终点t，现在还拥有k次免费路径特权，求从起点s到终点t的最短路。

分析： 这道题目是分层图最短路的经典应用，分层图就是由k个原图以及之前的某些边构成的一个新图，借用一下网上的示意图：

如图中所示，每层其实都是原图，层与层之间存在一些边权为0的单向边，若原图中点1与点0、点2相连，那么层间就会存在从上一层的点1到下一层的点0、点2的0权边。这样再跑最短路就实现了免费路径的特性，从0号点跑到3+n号点就是走了一次免费路径得到的最短路，从0号点跑到3+2*n号点就是走了两次免费路径得到的最短路。

所以这类问题解决方法大致也就清晰了，就是建图的时候多建几层图，不过在数据量小的时候这种方法没问题，当最大层数很大的时候就会浪费很多空间。实际上分层图就是加了一些0权边，大体都是和原图一致的，所以我们只建原图，并且牢记若点u到点v存在边那么也存在一条点u到下一层点v的0权边，同时有关数组多开一维记录层数，这样虽然没有建立实际的k层分层图，但通过原图就可以遍历分层图，最终效果是一致的。

最后要注意不能直接输出dis[t][k]，本来我以为也是免费路径越多最短路应该更优的，但是有些特殊情况可能用不到k条免费路径就已经达到了0，之后dis[t][i]会有一半情况为0，另一半不为0的奇偶分布情况，例如：2个点1条边，点0到点1之间存在一条边权为1的边，同时还有3次免费路径。

具体代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#define int long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;

int n, m, k, head[10005], dis[10005][15], cnt;//dis[i][j]表示到达i时使用了j次免费路径 
int s, t;
bool vis[10005][15];
struct edge
{
	int to, next, w;
}e[100005];

void add(int u, int v, int w)
{
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

void dijkstra()
{
	memset(dis, 0x3f, sizeof dis);
	dis[s][0] = 0;
	priority_queue<pii, vector<pii>, greater<pii> > a;
	a.push(make_pair(dis[s][0], s));
	while(a.size())
	{
		int now = a.top().second;
		int c = now/n;//表示在第几层上 
		now %= n;
		a.pop();
		if(vis[now][c]) continue;
		vis[now][c] = true;
		for(int i = head[now]; i; i = e[i].next)
		{
			int to = e[i].to;
			if(dis[to][c] > dis[now][c]+e[i].w)
			{
				dis[to][c] = dis[now][c]+e[i].w;
				a.push(make_pair(dis[to][c], to+c*n));
			}
		}
		if(c < k)
			for(int i = head[now]; i; i = e[i].next)
			{
				int to = e[i].to;
				if(dis[to][c+1] > dis[now][c])
				{
					dis[to][c+1] = dis[now][c];
					a.push(make_pair(dis[to][c+1], to+n*(c+1)));
				}
			}
	}
}

signed main()
{
	cin >> n >> m >> k >> s >> t;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%lld%lld%lld", &u, &v, &w);
		add(u, v, w), add(v, u, w);
	}
	dijkstra();
	//枚举最小值是因为可能用不到k条免费路径就已经达到了0，之后会有一半情况为0，另一半不为0 
	int ans = inf;
	for(int i = 0; i <= k; i++)
		ans = min(dis[t][i], ans);
	cout << ans << endl;
    return 0;
}