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

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

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.

题目分析：

第一道分层图最短路 f[to[i]][j]表示到了to[i]点,使用了j种免费航线的最短距离

f[to[i]][j]=min(f[to[i]][j],f[i][j]+val[i])

f[to[i]][j+1]=min(f[to[i]][j+1],f[i][j]),(j<k)

用Spfa进行转移 而且这题要堆优化

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k;
int start,end;
int head[200000];
int next[200000];
int to[200000];
int val[200000];
bool vis[20000][15];
int f[20000][15];
struct your
{
    int x,t;
};
int read()
{
    int sum=0;
    char c;
    c=getchar();
    while(c==' '||c=='\n')
        c=getchar();
    while(c<='9'&&c>='0')
        sum=(sum<<3)+(sum<<1)+(c-'0'),c=getchar();
    return sum;
}
struct cmp
{
	bool operator()(const your j,const your k)
	{
		return f[j.x][j.t]>f[k.x][k.t];
	} 
};
priority_queue<your,vector<your>,cmp>q;
void spfa()
{
    your nmp;
    nmp.x=start;
    nmp.t=0;
    memset(f,0x3f,sizeof f);
    f[start][0]=0;
    vis[start][0]=1;
    q.push(nmp);
    while(q.size())
    {
        nmp=q.top();
        q.pop();
        vis[nmp.x][nmp.t]=false;
        for(int i=head[nmp.x];i;i=next[i])
            if(f[to[i]][nmp.t]>f[nmp.x][nmp.t]+val[i])
            {
                f[to[i]][nmp.t]=f[nmp.x][nmp.t]+val[i];
                if(!vis[to[i]][nmp.t])
                {
                    your tmp;
                    tmp.x=to[i];
                    tmp.t=nmp.t;
                    vis[to[i]][nmp.t]=true;
                    q.push(tmp);
                }
            }
        if(nmp.t==k) continue;
        for(int i=head[nmp.x];i;i=next[i])
            if(f[to[i]][nmp.t+1]>f[nmp.x][nmp.t])
            {
                f[to[i]][nmp.t+1]=f[nmp.x][nmp.t];
                if(!vis[to[i]][nmp.t+1])
                {
                    your tmp;
                    tmp.x=to[i];
                    tmp.t=nmp.t+1;
                    vis[to[i]][nmp.t+1]=true;
                    q.push(tmp);
                }
            }
    }
}
int tot;
void add(int x,int y,int c)
{
    next[++tot]=head[x];
    to[tot]=y;
    val[tot]=c;
    head[x]=tot;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&start,&end);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        x=read();
        y=read();
        c=read();
        add(x,y,c);
        add(y,x,c);
    }
    spfa();
    int ans=0x7f7f7f7f;
    for(int i=0;i<=k;i++)
        ans=min(ans,f[end][i]);
    printf("%d",ans);
    return 0;
}