rt

分层图跑 dij

不太理解为什么会 TLE

#include<iostream>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
int n,m,k;
int st,ed;
const int N=5e4+10;
int dis[N][13];
int ver[N],ne[N],he[N],tot,edge[N];
void add(int u,int v,int w){
    ver[++tot]=v;
    edge[tot]=w;
    ne[tot]=he[u];
    he[u]=tot;
}
struct node{
    int id,w,k;
    bool operator <(const node &a)const{return w>a.w;}
};
bool vis[N][13];
priority_queue<node>q;
void dij(){
    memset(dis,0x3f,sizeof dis);
    dis[st][0]=0;
    q.push({st,0,0});
    while(!q.empty()){
        node h=q.top(); q.pop();
        int u=h.id,kk=h.k;
        if(vis[u][kk]) continue;
        vis[u][kk]=1;
        for(int i=he[u];i;i=ne[i]){
            int v=ver[i],w=edge[i];
            if(dis[v][kk]>dis[u][kk]+w){
                dis[v][kk]=dis[u][kk]+w;
                q.push({v,dis[v][kk],kk});
            }
            if(kk+1<=k && dis[v][kk+1]>dis[u][kk]){
                dis[v][kk+1]=dis[u][kk];
                q.push({v,dis[v][kk+1],kk+1});
            }
        }
    }
}
signed main(){
    cin>>n>>m>>k;
    cin>>st>>ed;
    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);
    }
    dij();
    int ans=1e9;
    for(int i=0;i<=k;++i) ans=min(ans,dis[ed][i]);
    cout<<ans<<endl;
    return 0;
}