又是一道分层图最短路的裸题

分层图最短路不会的戳这里这道题之需要把分层图最短路的方程稍微改一下就可以了。附一下代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define INF 2147483647

using namespace std;
struct node{
    int k,dis,used;
    bool operator < ( const node &x )const{return x.dis < dis;}
};
priority_queue<node> que;
long long n,m,k,s,t,d[50005],cnt,D[50005][60],v[50005][60]; 
struct Edge{
    int to,next,x;
}edge[2000005];
void add(int x,int y,int a)
{
    edge[++cnt].to = y;
    edge[cnt].x = a;
    edge[cnt].next = d[x];
    d[x] = cnt;
}
int main()
{
    int x,y,a;
    scanf(“%lld%lld%lld”,&n,&m,&k);
    s = 1; t = n;
    for(register int i = 1; i <= m; i++)
    {
        scanf(“%d%d%d”,&x,&y,&a);
        add(x,y,a);
        add(y,x,a);
    }
    que.push((node){s,0,0});
    for(register int i = 0; i <= n; i++)
        for(register int j = 0; j <= k; j++)
            D[i][j] = INF;
    D[s][0] = 0;
    while(!que.empty())
    {
        node u = que.top();
        que.pop();
        int kk = u.k,level = u.used;
        if(v[u.k][u.used]) continue;
        v[u.k][u.used] = 1;
        for(register int i = d[kk]; i; i = edge[i].next)
        {
        int too = edge[i].to;
        if(D[too][level] &gt; D[kk][level] + edge[i].x)
        {
            D[too][level] = edge[i].x + D[kk][level];
            que.push((node){too,D[too][level],level});
        }
        if(level &lt; k &amp;&amp; D[too][level + 1] &gt; D[kk][level] + edge[i].x / 2)
        {
            D[too][level + 1] = D[kk][level] + edge[i].x / 2;
            que.push((node){too,D[too][level + 1],level + 1});
        }
    }
}
long long  ans = INF;
for(register int i = 0; i &lt;= k; i++) ans = min(ans,D[t][i]);
printf("%lld\n",ans);
return 0;
}