【洛谷P4568】飞行路线【分层图最短路】

本文主要是介绍【洛谷P4568】飞行路线【分层图最短路】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P4568
一张无向图，每条边有权值，可以选择不超过$k$条路使这条路的权值变为0。求从$S$到$T$的最短路。

---

思路：

做这道题的原因：随机跳题$Part3$跳到了分层图最短路的题目$qwq$
这道题算是分成图最短路的模板吧。
由于题目中说有$k$条道路可以免费，所以直接跑最短路暴力判断显然是不行的。
分层图最短路就可以有效解决这种带有 「阶段性」的最短路。
我们把整个图分成$k+1$层（$0\sim k$），第$k$层表示已经将$k$条道路免费的图，也就是说，每一层的道路和普通的最短路没有什么区别，只是多了一些从第$i$层到第$i+1$层的道路。这些道路的权值为0，这样就有效解决了免费的情况，因为如果最短路跑到了第$i$层说明使$i$条道路免费了。
最终把每一层的终点连向一个超级汇点，权值为0，最短路就是第0层源点到超级汇点的最短路。
这道题还把我$spfa$卡了，敲了个$dij$才过。

---

代码：

#include <queue>
#include <cstdio>
#include <cstring>
#define mp make_pair
using namespace std;const int N=300010,M=3000100;
int n,m,k,S,T,T_,tot,head[N],dis[N];
bool vis[N];struct edge
{int next,to,dis;
}e[M];void add(int from,int to,int dis)
{e[++tot].to=to;e[tot].dis=dis;e[tot].next=head[from];head[from]=tot;
}void dij()
{memset(dis,0x3f3f3f3f,sizeof(dis));priority_queue<pair<int,int> > q;q.push(mp(0,S));dis[S]=0;while (q.size()){int u=q.top().second,v;q.pop();if (vis[u]) continue;vis[u]=1;for (int i=head[u];~i;i=e[i].next){v=e[i].to;if (dis[v]>dis[u]+e[i].dis){dis[v]=dis[u]+e[i].dis;q.push(mp(-dis[v],v));}}}
}int main()
{memset(head,-1,sizeof(head));scanf("%d%d%d%d%d",&n,&m,&k,&S,&T_);T=N-1; S++; T_++; k++;for (int i=1,x,y,z;i<=m;i++){scanf("%d%d%d",&x,&y,&z);x++; y++;for (int i=1;i<=k;i++){add(i*n-n+x,i*n-n+y,z);add(i*n-n+y,i*n-n+x,z);if (i<k){add(i*n-n+x,i*n+y,0);add(i*n-n+y,i*n+x,0);}}}for (int i=1;i<=k;i++)add(i*n-n+T_,T,0);dij();printf("%d\n",dis[T]);return 0;
}

这篇关于【洛谷P4568】飞行路线【分层图最短路】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---