分析：
比较裸的分层图最短路，我的实现方式是，每次求出1所有节点的最短路，之后用每一个节点更新与其相连的节点（取较小值），之后做K次，就求出了分层图的最短路了。
附上代码：
#include#include #include #include #include #include #include using namespace std;#define N 10005struct node{ int to,next,val;}e[N*10];int head[N],cnt,dis[N],vis[N],n,m,k;priority_queue < pair >q;void add(int x,int y,int z){ e[cnt].to=y; e[cnt].next=head[x]; e[cnt].val=z; head[x]=cnt++;}void Dijkstra(){ memset(vis,0,sizeof(vis)); while(!q.empty())q.pop();int num=0; for(int i=1;i<=n;i++)q.push(make_pair(-dis[i],i)); while(!q.empty()) { int x=q.top().second;q.pop(); if(vis[x])continue; vis[x]=1;num++; if(num==n)break; for(int i=head[x];i!=-1;i=e[i].next) { int to1=e[i].to; if(dis[to1]>dis[x]+e[i].val) { dis[to1]=dis[x]+e[i].val; q.push(make_pair(-dis[to1],to1)); } } }}int g[N];int main(){ memset(head,-1,sizeof(head)); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { int x,y,z;scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } memset(dis,0x3f,sizeof(dis));dis[1]=0; for(int i=0;i<=k;i++) { Dijkstra(); if(i!=k) { for(int x=1;x<=n;x++)g[x]=dis[x]; for(int x=1;x<=n;x++) { for(int j=head[x];j!=-1;j=e[j].next) { g[e[j].to]=min(dis[x],g[e[j].to]); } } for(int x=1;x<=n;x++)dis[x]=g[x]; } } printf("%d\n",dis[n]);}