分層圖最短路是指在可以進行分層圖的圖上解決最短路問題。
一般模型是：
在圖上，有k次機會可以直接通過一條邊，問起點與終點之間的最短路徑。
基本介紹
- 中文名：分層圖最短路問題
- 領域：計算機科學
概念：,模板,Input,Output,常規算法分析,正規解法：,
概念：
分層圖最短路是指在可以進行分層圖的圖上解決最短路問題。
一般模型是：
在圖上，有k次機會可以直接通過一條邊，問起點與終點之間的最短路徑。
模板
首先看一個問題：
在你的強力援助下，PCY 成功完成了之前的所有任務，他覺得，現在正是出去浪的大好時光。於是，他來到高速公路上，找到一輛摩的前往幾千公里以外他心儀的那家黃燜雞米飯。由於 PCY 的品味異於常人，途經幾百個城市的黃燜雞米飯他都不屑一顧，他只願意前往他心中最好的那家，但是為了一碗二十塊錢的黃燜雞米飯，他不願意花上幾千塊的路費，他希望路費儘量少。高速路上的警察叔叔被他的行為所打動，於是在多方協調下，最多 K 條城市之間的高速收費站願意免費為 PCY 放行（可以任意選擇）。
顯然，PCY 已經筋疲力盡，不想再動用自己的數學天才來計算他可以花費的最小路費，因此他希望你可以幫他最後一次，他說他可以請你吃大碗的黃燜雞米飯，還可以加一瓶豆奶。
現在給你 N 個城市 （編號為0 …N - 1 ），M 條道路，和每條高速公路的花費Wi ，以及題目所描述的 K。PCY 想從城市 S 到城市 T ，因為他對 T 城市的黃燜雞米飯情有獨鐘。
Input
第一行，三個整數 N ，M ，K ，如題意所描述
第二行，兩個整數 S ，T ，代表出發城市和目標城市編號
接下來 M 行，每行三個整數 X ，Y ，W ，代表 X 和 Y 城市之間的高速公路收費為 W 元
Output
共一行 ，輸出一個整數 ，代表PCY 最少需要花費的路費。
常規算法分析
我們擁有k次機會可以免費通過，所以我們可以設dis【i】【j】表示在還剩j次免花費機會的情況下到i的最小花費，然後在圖上進行一次SPFA，對dis【T】【i】取min即可
代碼：
#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<queue>using namespace std;const int MAXN=20010;const int INF=0x3f3f3f3f;struct node{ int next; int to; int w;} t[MAXN*10];bool vis[MAXN];int head[MAXN],num;int dis[MAXN][11];int n,m,k;int S,T,ans;void add(int x,int y,int z){ t[ ++num ].next=head[ x ]; t[ num ].to=y; t[ num ].w=z; head[ x ]=num;}void spfa( ){ queue<int> q; int x; q.push( S ); vis[ S ]=1; while( !q.empty() ) { x=q.front(); q.pop(); vis[ x ]=0; for(int i=head[ x ],y; i ; i=t[ i ].next) { y=t[ i ].to; if( dis[ x ][ k ]+t[ i ].w<dis[ y ][ k ] ) { dis[ y ][ k ]=dis[ x ][ k ]+t[ i ].w; if( !vis[ y ] ) vis[ y ]=1,q.push( y ); } for(int j=k-1; j>=0; j--) if( dis[ x ][ j ]+t[ i ].w<dis[ y ][ j ] || dis[ x ][ j+1 ]<dis[ y ][ j ] ) { dis[ y ][ j ]=min( min(dis[ x ][ j ]+t[ i ].w,dis[ x ][ j+1 ]),dis[ y ][ j ] ); if( !vis[ y ] ) vis[ y ]=1,q.push( y ); } } }}int main(){ int x,y,z; memset( dis,INF,sizeof dis); scanf("%d%d%d",&n,&m,&k); scanf("%d%d",&S,&T); for(int i=0; i<=k; i++) dis[ S ][ i ]=0; for(int i=1; i<=m; i++) { scanf("%d%d%d",&x,&y,&z); add( x,y,z ),add( y,x,z ); } spfa(); ans=INF; for(int i=0; i<=k; i++) ans=min( ans,dis[ T ][ i ] ); printf("%d\n",ans); return 0;}正規解法：
我們可以將這張圖分為k層，在每一層之間建立邊權為0的邊，這樣就能夠達到目的
代碼：
#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#define rg register#define ls 2*k#define rs 2*k+1using namespace std;const int MAXN=5000010;const int INF=0x3f3f3f3f;struct node{ int next; int to; int w;} t[MAXN];struct Heap{ int a[MAXN],dist[MAXN]; int tail; void clear() { tail=0; } void Swap(int x,int y) { swap( a[ x ],a[ y ] ); swap( dist[ x ],dist[ y ] ); } void insert(rg int id,rg int d) { a[ ++tail ]=id,dist[ tail ]=d; int tmp=tail; while( tmp>=2 ) { if( dist[ tmp ]<dist[ tmp/2 ] ) { Swap( tmp,tmp/2 ); tmp=tmp/2; } else break ; } } void update(rg int k) { int tmp=k; if( ls<=tail && dist[ ls ]<=dist[ tmp ] ) tmp=ls; if( rs<=tail && dist[ rs ]<=dist[ tmp ] ) tmp=rs; if( tmp!=k ) { Swap( k,tmp ); update( tmp ); } } int top( ) { return a[ 1 ]; } void pop( ) { a[ 1 ]=a[ tail ],dist[ 1 ]=dist[ tail-- ]; if( tail<=1 ) return ; update( 1 ); } int empty( ) { return tail; }} q;bool vis[MAXN];int head[MAXN],num;int dis[MAXN];int n,m,k;int S,T,ans=INF;inline int gi(){ int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f;}inline void add(int x,int y,int z){ t[ ++num ].next=head[ x ]; t[ num ].to=y; t[ num ].w=z; head[ x ]=num;}inline void dijkstra( ){ int x; memset( dis,INF,sizeof dis); q.clear(); dis[ S ]=0; q.insert( S,0 ); while( q.empty() ) { x=q.top(),q.pop(); if( vis[ x ] ) continue ; vis[ x ]=1; for(rg int i=head[ x ],y; i ;i=t[ i ].next ) { y=t[ i ].to; if( dis[ y ]>dis[ x ]+t[ i ].w && !vis[ y ] ) { dis[ y ]=dis[ x ]+t[ i ].w; q.insert( y,dis[ y ] ); } } }}int main(){ int x,y,z,t0,t1,t2; n=gi(),m=gi(),k=gi(),S=gi(),T=gi(); for(int i=1; i<=m; i++) { x=gi(),y=gi(),z=gi(); for(int j=0;j<=k;j++) { add( x+n*j,y+n*j,z ),add( y+n*j,x+n*j,z ); if( j<k ) add( x+n*j,y+n*(j+1),0 ),add( y+n*j,x+n*(j+1),0 ); } } dijkstra(); for(int i=0; i<=k; i++) ans=min( ans,dis[ T+i*n ] ); printf("%d\n",ans); return 0;}