本文主要是介绍【洛谷P4568】飞行路线【分层图最短路】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目大意:
题目链接:https://www.luogu.org/problemnew/show/P4568
一张无向图,每条边有权值,可以选择不超过 k k k条路使这条路的权值变为0。求从 S S S到 T T T的最短路。
思路:
做这道题的原因:随机跳题 P a r t 3 Part3 Part3跳到了分层图最短路的题目 q w q qwq qwq
这道题算是分成图最短路的模板吧。
由于题目中说有 k k k条道路可以免费,所以直接跑最短路暴力判断显然是不行的。
分层图最短路就可以有效解决这种带有 「阶段性」的最短路。
我们把整个图分成 k + 1 k+1 k+1层( 0 ∼ k 0\sim k 0∼k),第 k k k层表示已经将 k k k条道路免费的图,也就是说,每一层的道路和普通的最短路没有什么区别,只是多了一些从第 i i i层到第 i + 1 i+1 i+1层的道路。这些道路的权值为0,这样就有效解决了免费的情况,因为如果最短路跑到了第 i i i层说明使 i i i条道路免费了。
最终把每一层的终点连向一个超级汇点,权值为0,最短路就是第0层源点到超级汇点的最短路。
这道题还把我 s p f a spfa spfa卡了,敲了个 d i j dij 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】飞行路线【分层图最短路】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!