❤Aimee❤

和普通的最短路相比，多了一个免费边的限制

可以考虑得到，如果没有免费边的话，其实也就都一样了，那么考虑只有一个免费边

我们使用了之后，是不是就相当与进入了一个新的（没有边可以免费的）图，在这张图上，就和原来一样跑最短路就可以了

推而广之，结合一下dp的思想，可以把图分成$k$层，每用一条边升一层，不可下降

就有了分层图最短路

#include<iostream> 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m,pp,p;
const int maxn=200005; 
int dis[maxn][15];
int head[maxn];
int vis[maxn][15];
struct e{
    int to;
    int ne;
    int v;
}ed[maxn*5];
struct cit{
    int id;
    int fl;
    int dis;
    friend bool operator < (const cit x,const cit y){
        return x.dis>y.dis;
    }
};
priority_queue<cit> q;
cit u;
int s,t,k;
long long znx=(1<<29);
int x,y,z;
int maxx;
void add(int f,int t,int v){
    ed[++p].to=t;
    ed[p].ne=head[f];
    head[f]=p;
    ed[p].v=v;
}
long long dij(int s){
    memset(dis,127,sizeof(dis));
    memset(vis,0,sizeof(vis));
    maxx=dis[0][0];
    q.push((cit){
        s,0,0
    });
    dis[s][0]=0;
    while(!q.empty()){
         u=q.top();q.pop();
         if(vis[u.id][u.fl]) continue;
         vis[u.id][u.fl]=1;
        for(int i=head[u.id];i;i=ed[i].ne){
            int v=ed[i].to;
            if(dis[v][u.fl]>dis[u.id][u.fl]+ed[i].v&&!vis[v][u.fl]){
                    dis[v][u.fl]=dis[u.id][u.fl]+ed[i].v;
                q.push((cit){
                    v,u.fl,dis[v][u.fl]
                });
            }
            if(u.fl<k&&dis[v][u.fl+1]>dis[u.id][u.fl]&&!vis[v][u.fl+1]){
                dis[v][u.fl+1]=dis[u.id][u.fl];
                q.push((cit){
                    v,u.fl+1,dis[v][u.fl+1]
                });
            }
        }
    }
    long long Aimee=2147483647;
    for(int i=0;i<=k;++i){
        Aimee=min(Aimee,(long long)dis[t][i]);
    }
    return Aimee;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&s,&t);
    s++;
    t++;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&z);
        x++;
        y++;
        add(x,y,z);
        add(y,x,z);
    }
    cout<<dij(s);
    return 0;
}