大体思路和题解的差不多，但是是18pts（WA）

求求求调调调（颤音

Record

Code：

#include <bits/stdc++.h>
#define pii pair<int,int>
#define mkp(x,y) make_pair(x,y)
#define toNode(x,y) (x*n+y)
using namespace std;
const int maxn=1e4+5;
const int maxm=5e4+5;
const int maxk=22;
const int inf=0x3f3f3f3f;
struct edge{
    int to,w,next;
}e[4*maxm*maxk];
int n,m,k,tot,h[maxn*maxk],d[maxn*maxk];
bool vis[maxn*maxk];
priority_queue <pii,vector<pii>,greater<pii> > q;
inline void addEdge(int x,int y,int z){
    e[++tot]=(edge){y,z,h[x]};
    h[x]=tot;
}
inline void dijkstra(){
    memset(d,inf,sizeof(d));
    d[1]=0;
    q.push(mkp(0,1));
    while (!q.empty()){
        int now=q.top().second;
        q.pop();
        if (vis[now]) continue;
        vis[now]=true;
        for (int i=h[now];i;i=e[i].next){
            int v=e[i].to;
            if (d[v]>=d[now]+e[i].w){
                d[v]=d[now]+e[i].w;
                q.push(mkp(d[v],v));
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1,x,y,z;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        for (int j=0;j<=k;j++){
            addEdge(toNode(j,x),toNode(j,y),z);
            addEdge(toNode(j,y),toNode(j,x),z);
        }
        for (int j=0;j<k;j++){
            addEdge(toNode(j,x),toNode(j+1,y),0);
            addEdge(toNode(j,y),toNode(j+1,x),0);
        }
    }
    dijkstra();
    int ans=inf;
    for (int i=0;i<=k;i++) ans=min(ans,d[toNode(i,n)]);
    printf("%d\n",ans);
    return 0;
}

悬赏关注一枚