机房dalao推荐写的。。。（标签分层图）
经过前几题的分层图的洗礼，我深刻地体会到了分层图的优点和好处（主要是不想打dp....）
先说题吧....
很明确，模型是最短路，但是，怎么跑k个，是个问题....
解题过程：
1、先跑最短路，记录路径，然后找路径上的k条最长边，删掉
tips：贪心，很容易hack掉。
2、建两层的分层图（以前打的都是两层居多）
tips：会跑出0来....
solution：
主要就是：怎么连边喽....一开始老是卡住
连边有2种情况：
一共K层，上层可以跑到下层的出点，却不能回去，这就是一次免票。
然后跑最短路，最后查t+n*k那个点的dis就可以了。
for(int i=1;i<=m;i++) { int x,y,z; x=read();y=read();z=read(); addedge(x,y,z); addedge(y,x,z); for(int j=1;j<=k;j++) { addedge(x+n*j,y+n*j,z); addedge(y+n*j,x+n*j,z); addedge(x+(j-1)*n,y+j*n,0); addedge(y+(j-1)*n,x+j*n,0); } }
如上，分层连边。
之后就是一个spfa的事了（然而我各种常数（畜生）优化+O2卡到比旁边dalao快600ms的地步哈哈哈哈）
值得注意：
1、最后要把每一层的t点连在一起，因为如果在第二层就跑到了最短，在最后一层的t并不能查到正确答案
2、一共有k+1层，所以初始化dis要k+1层，因为这个卡了一小会...
#include<bits/stdc++.h> using namespace std; const int maxn=6e6+10; int n,m,k; int s,t; inline int read() { int x=0,f=1;char s=getchar(); while(s>‘9‘||s<‘0‘){if(s==‘-‘)f=-1;s=getchar();} while(s<=‘9‘&&s>=‘0‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } struct edge { int to,next,dis; }e[maxn]; int head[maxn],cnt; inline void addedge(int from,int to,int dis) { e[++cnt].next=head[from]; e[cnt].to=to; e[cnt].dis=dis; head[from]=cnt; } int dis[maxn],vis[maxn]; struct cmp { bool operator () (int a,int b) { return dis[a]>dis[b]; } }; priority_queue < int , vector < int > , cmp > q; //queue < int > q; void spfa(int s) { for(int i=0;i<=(k+1)*n;i++) { dis[i]=2147483647; vis[i]=0; } //memset(dis,0x3f,sizeof(dis)); q.push(s); dis[s]=0; vis[s]=1; while(!q.empty()) { //cout<<233; int u=q.top(); //int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dis[v]>dis[u]+e[i].dis) { dis[v]=dis[u]+e[i].dis; if(vis[v]==0) { q.push(v); vis[v]=1; } } } } } int main() { n=read(); m=read(); k=read(); s=read(); t=read(); for(int i=1;i<=m;i++) { int x,y,z; x=read(); y=read(); z=read(); addedge(x,y,z); addedge(y,x,z); for(int j=1;j<=k;j++) { addedge(x+n*j,y+n*j,z); addedge(y+n*j,x+n*j,z); addedge(x+(j-1)*n,y+j*n,0); addedge(y+(j-1)*n,x+j*n,0); } } for(int i=1;i<=k;i++) addedge(t+(i-1)*n,t+i*n,0); spfa(s); cout<<dis[t+k*n];//printf("%d",dis[t+k*n]); return 0; }
现在来说一说dp和分层图的关系：
首先，分层图的“层”是什么，它就是dp中的状态。在一些图论题目中，状态不好转移，就可以使用分层图进行转移，不需要再管“从哪转移”这个问题，剩下的最优解直接交给spfa就行了。（最优贸易）
这些状态之间可以互相转移，一般在二维或是以上，可以省去一些不相关状态的枚举，但是因为spfa的广泛枚举性还是会枚举更多“不是最优解”的状态的。
（完）
原文：https://www.cnblogs.com/ajmddzp/p/11503135.html