Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？
对于30%的数据,2<=n<=50,1<=m<=300,k=0;
对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1;
对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10.
HOME Back
洛谷上面的数据卡常毒瘤啊！！巴中随手a，洛谷交了快10次...加了一些玄学优化...
spfa里面如果当前状态的cost已经大于等于到终点时的相同状态的cost，就不把这个状态加入队列了。然后就是RG大法好！！
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define RG register 6 using namespace std; 7 8 int n, k, m, s, t; 9 int dp[10005][15]; 10 11 struct node { 12 int u, k; 13 node ( int u, int k ) : 14 u ( u ), k ( k ) { } 15 }; 16 17 int stot, nex[100005], h[10005], tov[100005], w[100005]; 18 void add ( int u, int v, int ss ) { 19 tov[++stot] = v; 20 w[stot] = ss; 21 nex[stot] = h[u]; 22 h[u] = stot; 23 } 24 25 int vis[10005][15]; 26 queue < node > q; 27 28 void spfa ( ) { 29 memset ( dp, 0x3f3f3f3f, sizeof ( dp ) ); 30 vis[s][0] = 1; 31 dp[s][0] = 0; 32 q.push ( node ( s, 0 ) ); 33 while ( !q.empty ( ) ) { 34 node x = q.front ( ); q.pop ( ); vis[x.u][x.k] = 0; 35 for ( RG int i = h[x.u]; i; i = nex[i] ) { 36 int v = tov[i]; 37 if ( dp[v][x.k] > dp[x.u][x.k] + w[i] ) { 38 dp[v][x.k] = dp[x.u][x.k] + w[i]; 39 if ( !vis[v][x.k] && dp[v][x.k] <= dp[t][x.k] ) { 40 vis[v][x.k] = 1; 41 q.push ( node ( v, x.k ) ); 42 } 43 } 44 if ( x.k < k && dp[v][x.k+1] > dp[x.u][x.k] ) { 45 dp[v][x.k+1] = dp[x.u][x.k]; 46 if ( !vis[v][x.k+1] && dp[v][x.k+1] <= dp[t][x.k+1] ) { 47 vis[v][x.k+1] = 1; 48 q.push ( node ( v, x.k + 1 ) ); 49 } 50 } 51 } 52 } 53 } 54 55 int main ( ) { 56 scanf ( "%d%d%d", &n, &m, &k ); 57 scanf ( "%d%d", &s, &t ); 58 for ( RG int i = 1; i <= m; i ++ ) { 59 int u, v, s; 60 scanf ( "%d%d%d", &u, &v, &s ); 61 add ( u, v, s ); 62 add ( v, u, s ); 63 } 64 spfa ( ); 65 printf ( "%d", dp[t][k] ); 66 return 0; 67 }
【BZOJ2763/洛谷p4563】【分层图最短路】飞行路线
原文：https://www.cnblogs.com/wans-caesar-02111007/p/9478194.html