显然的分层图
设 dis [ i ] [ j ] 表示到点 i ， 已经建立了 j 条高速公路的最短距离
然后转移每次都分建立高速公路和不建立高速公路两种情况
跑Djikstra
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7,M=1e5+7; int n,m,K,ans=2e9+7; int fir[N],from[M<<2],to[M<<2],val[N<<2],cntt; inline void add(int &a,int &b,int &c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; } struct node//存当前状态的结构体 { int pos,dis,cnt;//当前的位置，已经走的距离，建立了几条高速公路 inline bool operator < (const node &tmp) const { return dis>tmp.dis; } }; priority_queue <node> q; int dis[N][27]; void Dijk() { memset(dis,127,sizeof(dis)); q.push((node){1,0,0}); dis[1][0]=0;//初始状态 node x; while(!q.empty()) { x=q.top(); q.pop(); if(dis[x.pos][x.cnt]!=x.dis) continue; for(int i=fir[x.pos];i;i=from[i]) { int &v=to[i]; if(dis[v][x.cnt]>dis[x.pos][x.cnt]+val[i])//不建立高速公路 { dis[v][x.cnt]=dis[x.pos][x.cnt]+val[i]; q.push((node){v,dis[v][x.cnt],x.cnt}); } if(x.cnt<K&&dis[v][x.cnt+1]>dis[x.pos][x.cnt])//建立高速公路 { dis[v][x.cnt+1]=dis[x.pos][x.cnt]; q.push((node){v,dis[v][x.cnt+1],x.cnt+1}); } } } } int main() { int a,b,c; n=read(); m=read(); K=read(); for(int i=1;i<=m;i++) { a=read(); b=read(); c=read(); add(a,b,c); add(b,a,c); } Dijk(); for(int i=0;i<=K;i++) ans=min(ans,dis[n][i]);//取个min printf("%d",ans); return 0; }