代码结果

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10,M=5e5+10;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][100];
bool st[N][100];
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
struct td{
    int u,d,now;
    friend bool operator <(td a,td b){
        return a.d>b.d;
    }
};
int n,m,k;
void dij(){
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    priority_queue<td>q;
    q.push({1,0,0});
    dist[1][0]=0;
    while(q.size()){
        int u=q.top().u,now=q.top().now;
        q.pop();
        if(st[u][now])continue;
        st[u][now]=1;
        for(int i=h[u];~i;i=ne[i]){
            int j=e[i];
            if(!st[j][now+1]&&dist[j][now+1]>dist[u][now]+w[i]/2&&now<k){
                dist[j][now+1]=dist[u][now]+w[i]/2;
                q.push({j,dist[j][now+1],now+1});
            }
            if(!st[j][now]&&dist[j][now]>dist[u][now]+w[i]){
                dist[j][now]=dist[u][now]+w[i];
                q.push({j,dist[j][now],now});
            }
        }
    }
}
int main(){
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n, &m, &k);
    while (m -- ){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a, b, c);
        add(b, a, c);
    }
    dij();
    int ans=1e9;
    for(int i=0;i<=k;i++){
        ans=min(ans,dist[n][i]);
        //cout<<dist[n][i]<<endl;
    }
    if(n<=k)puts("0");
    else cout<<ans;
    return 0;
}

三倍经验来的