一般建图时会给定节点数 n 和边数 m,然后可以写出利用邻接矩阵、邻接表、链式前向星等等建图的代码。
在构建了一张图的基础上,我们将图再复制 k 份,形成了k+1 层图,这就是所谓分层图。可以将分层图理解为多个平行的图。
一般模型的是:在一张图上,可以进行 k 次决策,对于每次决策,不影响图的结构,只影响目前的状态或代价。我们可以构建 k+1 层图,做出一次决策可能意味着跨越层级,一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边,表示付出该代价后就可以转换状态了。
如图,cost 就是做出跨越层级的决策后产生的代价。
建图方式
有 n 个节点时,[1,n] 表示第 $1 $ 层,[1+n,2n] 代表第二层,[1+2n,3n] 代表第三层,[1+(i−1)n,in] 代表第 i 层。每一层之间的连边就需要具体问题具体分析了。
Alice 和 Bob 现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在 n 个城市设有业务,设这些城市分别标记为 0 到 n−1,一共有 m 种航线,每种航线连接两个城市,并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多 k 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少?
输入格式
第一行三个整数 n,m,k,分别表示城市数,航线数和免费乘坐次数。
接下来一行两个整数 s,t,分别表示他们出行的起点城市编号和终点城市编号。
接下来 m 行,每行三个整数 a,b,c,表示存在一种航线,能从城市 a 到达城市 b,或从城市 b 到达城市 a,价格为 c。
输出格式
输出一行一个整数,为最少花费。
输入输出样例
输入 #1
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
输出 #1
8
说明/提示
数据规模与约定
对于 $30\%$ 的数据,2≤n≤50,1≤m≤300,k=0。
对于 $50\%$ 的数据,$2 \le n \le 600,1 \le m \le 6\times10^3,0 \le k \le 1$2。
对于 $100\%$ 的数据,2≤n≤104,1≤m≤5×104,0≤k≤10,0≤s,t,a,b≤n,a=b,0≤c≤103。
另外存在一组 hack 数据。
分析
由于有 k 次免费乘坐飞机的机会,那么对于一条边上的一个点对 (u,v),在起点 u 上有两种选择:是否选择免费乘坐,如果免费乘坐会使得 k 减一。如果选择免费乘坐,我们就从 u 走到下一层的 v 。也就是说,我们可以建立 k+1 层图。各层内部正常连边,各层之间从上到下连权值为 0 的单向边。每向下跑一层,就相当于免费搭一次飞机,当跑到第 k+1 层图,k 次免费乘坐的机会就用完了。当然,不一定非要把 k 次机会用完, 利用 Dijkstra 算法求得从 s 到 t,t+n,⋯,t+kn 的单源最短路径长度,然后从中取最小即可。
There are N cities in the country, and M directional roads from u to v(1≤u,v≤n). Every road has a distance ci . Haze is a Magical Girl that lives in City 1, she can choose no more than K roads and make their distances become 0. Now she wants to go to City N, please help her calculate the minimum distance.
Input
The first line has one integer T(1≤T≤5), then following T cases.
For each test case, the first line has three integers N,M and K.
Then the following MM lines each line has three integers, describe a road, Ui,Vi,Ci. There might be multiple edges between u and v.
It is guaranteed that N≤100000,M≤200000,K≤10,0≤Ci≤109.
There is at least one path between City 1 and City N.
小雨所在的城市一共有 m 条地铁线,分别标号为 1 号线,2 号线 …… m 号线。整个城市一共有 n 个车站,编号为 1∼n 。其中坐 i 号线需要花费 ai 的价格,每坐一站就需要多花费 bi 的价格。i 号线有 ci 个车站,而且这 ci 个车站都已知,如果某一站有多条地铁线经过,则可以在这一站换乘到另一条地铁线,并且能多次换乘。现在小雨想从第 s 个车站坐地铁到第 t 个车站,地铁等待时间忽略不计,求最少花费的价格,若不能到达输出 −1 。地铁是双向的,所以 s 可能大于 t。
输入描述
第一行输入四个正整数 n,m,s,t,分别表示车站个数,地铁线数,起点站和终点站。
第二行到第 m+1 行,每行前三个数为 ai,bi,ci,分别表示坐 i 号线的价格,i 号线每坐一站多花的价格,i 号线车站个数。接下来 ci 个数,表示 i 号线的每一个车站的编号,单调递增。
分层图作为一种建图技巧,技巧性较强,此处的建图方式非常高明。
每条地铁线路可以看做一层图,对于第 i 层图,只要建立第 i 条地铁线即可。但是由于换乘站的情况存在,每层之间可能是相连的,如果处理每一层相连的点,就会显得相当麻烦。
对应每个车站,我们可以设立一个虚点。只要每层的车站与对应的虚点连接即可。那么分层图中,1∼m 层是 m 条地铁线,m+1 层都是虚点,实点到虚点代价都是 0,虚点到实点代价是对应的 ai,这样就能起到换乘的效果。
设立虚点后,不用根据层与层间连边;否则这样每层都要连边,就要 m2n 条边;而设立虚点只要 2nm 条边,大大降低了时间复杂度。同时也方便了计算,直接从 s 的虚点到 t 的虚点的最短路就是答案;如果不设虚点,要对应每个车站 s 的地铁到每个车站 t 的地铁求最短路。
如图,从 x 到 y 就是一个经过虚点换乘的过程。如果 x 想通过换乘到达 z,但是换乘后的地铁线路上显然没有 z 这个站点,那么距离为无穷大,自然不是最短路;同样的, Dijkstra 算法的原理也不会产生一个点 x 在其虚点和实点之间反复横跳的情况。