据说这个叫分层图最短路 是个常见套路 一般就是：有k次机会可以直接通过一条边,问起点与终点之间的最短路径
我的理解：就相当给dis和inque数组加了一维表示用了j次免费机会 然后在松弛的时候就有两种决策：1.走免费边 2.走要钱的边
8102年了 别写spfa了
#include<bits/stdc++.h> #define N 10005 #define M 50005 #define K 12 #define INF 0x3f3f3f3f using namespace std; template <class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } struct Edge { int to,next,val; }edge[2*M]; int n,m,k,s,t,first[N],tot; inline void addedge(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].val=z; edge[tot].next=first[x]; first[x]=tot; } int dis[N][K]; //到了i 用了j次免费机会的最短路 bool inque[N][K]; //到达i 用了j次免费机会的情况是否出现过. struct Graph { int num,d,tic; bool operator <(const Graph &a) const { return d>a.d; } }; void Dijkstra() { memset(dis,0x3f,sizeof(dis)); dis[s][0]=0; priority_queue<Graph> q; q.push((Graph){s,0,0}); while(!q.empty()) { int now=q.top().num,ti=q.top().tic; q.pop(); if(inque[now][ti]) continue; inque[now][ti]=true; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(ti<k&&!inque[vis][ti+1]&&dis[vis][ti+1]>dis[now][ti]) //走免费路 { dis[vis][ti+1]=dis[now][ti]; q.push((Graph){vis,dis[vis][ti+1],ti+1}); } if(!inque[vis][ti]&&dis[vis][ti]>dis[now][ti]+edge[u].val) { dis[vis][ti]=dis[now][ti]+edge[u].val; q.push((Graph){vis,dis[vis][ti],ti}); } } } } int main() { read(n); read(m); read(k); read(s); read(t); s++,t++; for(int i=1,x,y,z;i<=m;i++) { read(x); read(y); read(z); x++,y++; addedge(x,y,z); addedge(y,x,z); } Dijkstra(); int ans=INF; for(int i=0;i<=k;i++) ans=min(ans,dis[t][i]); cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9849755.html
