分层图分K层，层之间是升级道路，跑最短路就行了
据说卡spfa
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 10010 #define MAXM 500010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long struct vec{ int to; int fro; int v; }; struct pt{ int x; int y; ll v; pt(int _x,int _y,ll _v){ x=_x; y=_y; v=_v; } friend bool operator <(pt x,pt y){ return x.v>y.v; } }; vec mp[MAXM*2]; int tai[MAXN*21],cnt; int n,m,k; ll dis[MAXN][21]; bool vis[MAXN][21]; priority_queue<pt>q; inline void be(int x,int y,int z){ mp[++cnt].to=y; mp[cnt].fro=tai[x]; tai[x]=cnt; mp[cnt].v=z; } inline void bde(int x,int y,int z){ be(x,y,z); be(y,x,z); } void dijkstra(){ int i,x,X,y; memset(dis,0x3f,sizeof(dis)); dis[1][0]=0; q.push(pt(1,0,0)); while(!q.empty()){ x=q.top().x; X=q.top().y; q.pop(); if(vis[x][X]){ continue ; } vis[x][X]=1; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(dis[y][X]>dis[x][X]+mp[i].v){ dis[y][X]=dis[x][X]+mp[i].v; q.push(pt(y,X,dis[y][X])); } if(X!=k&&dis[y][X+1]>dis[x][X]){ dis[y][X+1]=dis[x][X]; q.push(pt(y,X+1,dis[y][X+1])); } } } } int main(){ int i,x,y,z; scanf("%d%d%d",&n,&m,&k); while(m--){ scanf("%d%d%d",&x,&y,&z); bde(x,y,z); } dijkstra(); ll ans=dis[n][0]; for(i=1;i<=k;i++){ ans=min(ans,dis[n][i]); } printf("%lld\n",ans); return 0; } /* 4 4 1 1 2 10 2 4 10 1 3 1 3 4 100 */
