Solution

建立 \(k+1\) 层图跑 \(Dijkstra\) 就好了.

Code

#include
    
     #define ll long longusing namespace std;const int maxn=200008;int n,m,k,s,t;struct sj{    int to;    int next;    int w;}a[maxn*10];int head[maxn],size;ll dis[maxn],dist[maxn];void add(int x,int y,int w){    a[++size].to=y;    a[size].next=head[x];    head[x]=size;    a[size].w=w;}int read(){    char ch=getchar(); int f=1,w=0;    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}    return f*w;}struct node {    int u;ll d;    bool operator <(const node& rhs) const {        return d>rhs.d;    }};inline void Dijkstra(){    memset(dis,127,sizeof(dis));    dis[s]=0;    priority_queue
     
       q;    q.push((node){s,0});    while(!q.empty())    {        node xx=q.top(); q.pop();        int u=xx.u,d=xx.d;        if(d!=dis[u])continue;        for(int i=head[u];i;i=a[i].next)        {            int tt=a[i].to,w=a[i].w;            if(dis[u]+w