题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2662
这种的都是分层图。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=55,M=1005; int n,m,K,hd[N],xnt,dis[N][N],ans=0x3f3f3f3f; bool vis[N][N]; struct Ed{ int nxt,to,w; Ed(int n=0,int t=0,int w=0):nxt(n),to(t),w(w) {} }ed[M<<1]; struct Node{ int c,a,b; Node(int c=0,int a=0,int b=0):c(c),a(a),b(b) {} bool operator< (const Node &b)const {return c>b.c;} }; void add(int x,int y,int z) { ed[++xnt]=Ed(hd[x],y,z);hd[x]=xnt; ed[++xnt]=Ed(hd[y],x,z);hd[y]=xnt; } priority_queue<Node> q; void dj() { memset(dis,0x3f,sizeof dis); dis[1][0]=0; q.push(Node(0,1,0)); while(q.size()) { int a=q.top().a,b=q.top().b;q.pop(); while(q.size()&&vis[a][b])a=q.top().a,b=q.top().b,q.pop(); if(vis[a][b])break;vis[a][b]=1; for(int i=hd[a],v;i;i=ed[i].nxt) { if(dis[v=ed[i].to][b]>dis[a][b]+ed[i].w) dis[v][b]=dis[a][b]+ed[i].w,q.push(Node(dis[v][b],v,b)); if(b<K&&dis[v][b+1]>dis[a][b]+(ed[i].w>>1)) dis[v][b+1]=dis[a][b]+(ed[i].w>>1),q.push(Node(dis[v][b+1],v,b+1)); } } } int main() { scanf("%d%d%d",&n,&m,&K); int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); } dj(); for(int i=0;i<=K;i++)ans=min(ans,dis[n][i]); printf("%d ",ans); return 0; }