分层图最短路小记 |
您所在的位置:网站首页 › twP4568 › 分层图最短路小记 |
分层图最短路小记 Liu Zhe 10月 15, 2019 图论最短路径 浏览量 分享到微博 分享到 Twitter 分享到 Facebook 分享到 Google+ 分享到 LinkedIn 分享到 QQ 分享到 Telegram分层图最短路,顾名思义,是一种在分层图下求最短路的方法。 一般模型是: 在图上,有k次机会可以直接通过一条边,问起点与终点之间的最短路径。 例题 JLOI2011 飞行路线 (洛谷P4568 )题目描述Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务,设这些城市分别标记为00到n-1n−1,一共有mm种航线,每种航线连接两个城市,并且航线有一定的价格。 Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多kk种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少? 输入格式数据的第一行有三个整数,n,m,kn,m,k,分别表示城市数,航线数和免费乘坐次数。第二行有两个整数,s,ts,t,分别表示他们出行的起点城市编号和终点城市编号。接下来有m行,每行三个整数,a,b,ca,b,c,表示存在一种航线,能从城市aa到达城市bb,或从城市bb到达城市aa,价格为cc。 输出格式只有一行,包含一个整数,为最少花费。 解法一(DP)还记得最短路么? 最短路的状态是这么转移的: 而在分层图最短路中,我们可以开一个二维的$dis_i,_j$,表示到起始节点到$i$号节点,已使用$j$次机会的代价。 于是我们便得到了这么一个状态转移方程: 代码大致和dijkstra差不多,我就只贴dijkstra的代码了。 代码大致如下: struct Heap { int u, v, now; bool operator b.v; } }; inline void dijkstra(int x) { dis[x][0] = 0; priority_queue q; q.push((Heap){x, 0, 0}); while (!q.empty()) { int u = q.top().u; int now = q.top().now; q.pop(); if (vis[u][now]) //vis也要开二维 continue; vis[u][now] = true; for (register int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (!vis[v][now + 1] && now < k && dis[v][now + 1] > dis[u][now]) //使用免费机会 { dis[v][now + 1] = dis[u][now]; q.push((Heap){v, dis[v][now + 1], now + 1}); } if (!vis[v][now] && dis[v][now] > dis[u][now] + edge[i].data) //不使用免费机会 { dis[v][now] = dis[u][now] + edge[i].data; q.push((Heap){v, dis[v][now], now}); } } } } 解法二 不推荐 (真·分层图)这种做法很好写,也很好理解,不过浪费时空: 一下是几张张评测时的图片: 做法一 做法二 思想大致是: 我们如果有k次免费的机会,那我们就建k层图。 各层内部正常连边,各层之间从上到下连权值为0的边。每向下跑一层,就相当于免费使用一次机会。 代码不太重要就不贴了其实不会写(,可以去Payphone—X同学的Blog康。 Code For JLOI2011#include #include #include #include #define maxn 50005 #define endl '\n' using namespace std; struct node { int to, next, data; } edge[maxn dis[u][now]) { dis[v][now + 1] = dis[u][now]; q.push((Heap){v, dis[v][now + 1], now + 1}); } if (!vis[v][now] && dis[v][now] > dis[u][now] + edge[i].data) { dis[v][now] = dis[u][now] + edge[i].data; q.push((Heap){v, dis[v][now], now}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> k >> s >> t; for (register int i = 1; i > x >> y >> v; add_edge(x, y, v); add_edge(y, x, v); } for (register int i = 0; i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |