这题显然一看就是要跑最短路的嘛233333
但是这题有个关键限制条件，就是
可以免费在最多k种航线上搭乘飞机
因此我们不能直接建图，需要考虑一些特殊的建图方法。没错，就决定是你了，分层图。
注意到k<=10，于是我们考虑把u点拆分，把到u点时用过的免费次数加入其中。也就是如果用i表示这一个点用过的免费次数，则加边（u,v）时，还要加上（u + i * n,v + (i + 1) * n），边权为0，即我在u到v时使用了一次免费次数。这样我们就可以构建出一个含有多层的图。然后愉快的跑dijkstra就行。
统计答案的时候，我们对dis[t + i * n]进行取最小值，也就是对所有用i次免费到达t的费用取一个最小值就是最终答案了。
这题唯一的难点就是建图的过程，只要掌握好建分层图的方法，然后就可以直接上板子了。复杂度O(kmlogn)，可以通过。
#include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<algorithm> #define N 1000010 #define M 5000010 using namespace std; int head[N],nxt[M],to[M],val[M]; int n,m,cnt; void Add(int u,int v,int w) { nxt[++cnt] = head[u]; head[u] = cnt; to[cnt] = v; val[cnt] = w; return; } int k,s,t; int dis[N]; struct qwq { int u,dis; bool operator < (const qwq &a) const { return dis > a.dis; } }top,node; priority_queue<qwq>q; const int inf = 100000010; bool vis[N]; void dijkstra() { for(int i = 0;i <= n + k * n;i++) dis[i] = inf; dis[s] = 0; top.u = s; top.dis = 0; q.push(top); while(q.size()) { top = q.top(); q.pop(); int u = top.u; if(!vis[u]) { vis[u] = 1; for(int i = head[u];i;i = nxt[i]) { int v = to[i]; if(dis[v] > dis[u] + val[i]) { dis[v] = dis[u] + val[i]; node.u = v,node.dis = dis[v]; q.push(node); } } } } return; } int main() { scanf("%d %d %d",&n,&m,&k); scanf("%d %d",&s,&t); for(int j = 1;j <= m;j++) { int u,v,w; scanf("%d %d %d",&u,&v,&w); Add(u,v,w); Add(v,u,w); for(int i = 1;i <= k;i++) { Add(u + (i - 1) * n,v + i * n,0); Add(v + i * n,u + i * n,w); Add(v + (i - 1) * n,u + i * n,0); Add(u + i * n,v + i * n,w); } } dijkstra(); int ans = inf; for(int i = 0;i <= k;i++) ans = min(dis[t + i * n],ans); printf("%d",ans); return 0; }
原文：https://www.cnblogs.com/lijilai-oi/p/10901973.html