HYSBZ - 2763 飞行路线 （分层图+spfa）

首先我们先来看一下什么叫做分层图：

        分层图主要是应用于 变化的最短路问题 问题常表现为一个最短路问题上加一些手脚，如减小一些边权，改变一些连接，但事先又不知道，或可以自由选择改变哪个边，最终求最短路等等。由于无法知道改变了那些边，所以用到分层图思想。
可以理解为 平行宇宙 一样的东西 就是把原图复制出来k个，然后在原图连接的基础上，在相邻层中间加一些要求的变化边，通常是单向的（保证从每一层到下一层不再回来），再跑最短路。

                                                                                    ------来自（https://blog.csdn.net/herekigo/article/details/62851877） 

        其实我们就可以理解成，暴力一下就是，只不过在spfa中遍历的元素不止包含着此时的城市，还有此时已经用过的免费的次数，这样来进行我们的spfa就好了；

2763: [JLOI2011]飞行路线

时间限制: 10 Sec  内存限制: 128 MB
提交: 4408  解决: 1707
[提交][][]

题目描述

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)

输出

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

样例输入

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

样例输出

8

提示

对于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.

#include<cstdio>
#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
using namespace std;
#define inf 0x3f3f3f
struct ***
{
	int to, len, ne;
}ed[100005];
int vis[10005][12];
int d[10005][12];
int head[10005];
int cnt = 0, n, m, k, st, en;
void init()
{
	memset(vis, 0, sizeof(vis));
	for (int s = 0; s <= n; s++)
	{
		for (int w = 0; w <= k; w++)
		{
			d[s][w] = inf;
		}
		head[s] = -1;
	}
	cnt = 0;
}
void add(int from, int to, int len)
{
	ed[cnt].to = to;
	ed[cnt].len = len;
	ed[cnt].ne = head[from];
	head[from] = cnt++;
}
void spfa()
{
	d[st][0] = 0;
	vis[st][0] = 1;
	queue< pair<int,int> >q;
	q.push(make_pair(st, 0));
	while (!q.empty())
	{
		pair<int, int>t = q.front();
		q.pop();
		vis[t.first][t.second] = 0;
		for (int s = head[t.first]; ~s; s = ed[s].ne)
		{
			if (d[t.first][t.second] + ed[s].len < d[ed[s].to][t.second])
			{
				d[ed[s].to][t.second] = d[t.first][t.second] + ed[s].len;
				if (!vis[ed[s].to][t.second])
				{
					vis[ed[s].to][t.second] = 1;
					q.push(make_pair(ed[s].to, t.second));
				}
			}
			if (d[t.first][t.second] < d[ed[s].to][t.second+1]&&t.second<k)
			{
				d[ed[s].to][t.second+1] = d[t.first][t.second];
				if (!vis[ed[s].to][t.second+1])
				{
					vis[ed[s].to][t.second+1] = 1;
					q.push(make_pair(ed[s].to, t.second+1));
				}
			}
		}
	}
}
int main()
{
	while (~scanf("%d%d%d", &n, &m, &k))
	{
		init();
		scanf("%d%d", &st, &en);
		while (m--)
		{
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c);
			add(b, a, c);
		}
		spfa();
		printf("%d\n", d[en][k]);
	}
	return 0;
}