分层图

概述

一般建图时会给定节点数 nn 和边数 mm，然后可以写出利用邻接矩阵、邻接表、链式前向星等等建图的代码。
在构建了一张图的基础上，我们将图再复制 kk 份，形成了k+1k+1 层图，这就是所谓分层图。可以将分层图理解为多个平行的图。
一般模型的是：在一张图上，可以进行 kk 次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。我们可以构建 k+1k+1 层图，做出一次决策可能意味着跨越层级，一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以转换状态了。

如图，cost\text{cost} 就是做出跨越层级的决策后产生的代价。

建图方式

有 nn 个节点时，[1,n][1,n] 表示第 $1 $ 层，[1+n,2n][1+n,2n] 代表第二层，[1+2n,3n][1+2n,3n] 代表第三层，[1+(i−1)n,in][1+(i-1)n,in] 代表第 ii 层。每一层之间的连边就需要具体问题具体分析了。

分层图最短路

思想

建立分层图是对具体问题的一种建图策略，对于多种决策的最短路问题往往能产生奇效。
如果每次选择路线除了选择边还有其他的决策，我们不妨把决策转化为新的一条边，将其赋予特殊的边权，最后求最短路就能得到最小的代价。

洛谷 P4568 [JLOI2011]飞行路线 ↬\looparrowright

题目描述

Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 nn 个城市设有业务，设这些城市分别标记为 00 到 n−1n-1，一共有 mm 种航线，每种航线连接两个城市，并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 kk 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

输入格式

第一行三个整数 n,m,kn,m,k，分别表示城市数，航线数和免费乘坐次数。
接下来一行两个整数 s,ts,t，分别表示他们出行的起点城市编号和终点城市编号。
接下来 mm 行，每行三个整数 a,b,ca,b,c，表示存在一种航线，能从城市 aa 到达城市 bb，或从城市 bb 到达城市 aa，价格为 cc。

输出格式

输出一行一个整数，为最少花费。

输入输出样例

输入 #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=02 \le n \le 50,1 \le m \le 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≤1032 \le n \le 10^4,1 \le m \le 5\times 10^4,0 \le k \le 10,0\le s,t,a,b\le n,a\ne b,0\le c\le 10^3。
另外存在一组 hack 数据。

分析

由于有 kk 次免费乘坐飞机的机会，那么对于一条边上的一个点对 (u,v)(u,v)，在起点 uu 上有两种选择：是否选择免费乘坐，如果免费乘坐会使得 kk 减一。如果选择免费乘坐，我们就从 uu 走到下一层的 vv 。也就是说，我们可以建立 k+1k+1 层图。各层内部正常连边，各层之间从上到下连权值为 00 的单向边。每向下跑一层，就相当于免费搭一次飞机，当跑到第 k+1k+1 层图，kk 次免费乘坐的机会就用完了。当然，不一定非要把 kk 次机会用完， 利用 Dijkstra\text{Dijkstra} 算法求得从 ss 到 t,t+n,⋯ ,t+knt,t+n,\cdots,t+kn 的单源最短路径长度，然后从中取最小即可。

如图为根据样例建立的分层图，第 ii 层与第 i+1i+1 层之间有边权为 00 的单向边连接 。

代码

代码中规定节点编号从 11 到 nn。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<queue>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 10002
#define M 50002
#define K 50
using namespace std;
/*---=====链式前向星=====---*/
struct E
{
	int to;
	int w;
	int Next;
}edge[M*K<<1];
int head[N*K],tot;
/*------------------------*/
int n,m,k;
int s,t;
int dis[N*K];
bool vis[N*K];
inline void add(int u,int v,int w)//加边
{
	tot++;
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].Next=head[u];
	head[u]=tot;
}
struct node
{
	int id;
	int dis;
	bool operator<(const node &x)const
	{
		return x.dis<dis;
	}
};
/*-----=======单源最短路径模板=======-----*/
void dijkstra()
{
	memset(dis,0x3f,sizeof(dis));//初始化
	dis[s]=0;
	int i;
	priority_queue<node>q;
	q.push((node){s,0});
	while(!q.empty())
	{
		node now=q.top();
		q.pop();
		int x=now.id;
		if(vis[x]) continue;
		vis[x]=1;
		for(i=head[x];~i;i=edge[i].Next)
		{
			int y=edge[i].to;
			if(!vis[y]&&dis[y]>dis[x]+edge[i].w)
			{
				dis[y]=dis[x]+edge[i].w;
				q.push((node){y,dis[y]});
			}
		}
	}
}
int main()
{
	cin>>n>>m>>k>>s>>t;
	int i;
	s++;
	t++;
	memset(head,-1,sizeof(head));
	while(m--)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		u++;
		v++;
		add(u,v,w);
		add(v,u,w);
		for(i=1;i<=k;i++)//建立分层图
		{
			//第i+1层建边
			add(n*i+u,n*i+v,w);
			add(n*i+v,n*i+u,w);
			//两层之间建边
			add(n*(i-1)+u,n*i+v,0);
			add(n*(i-1)+v,n*i+u,0);
		}
	}
	dijkstra();
	int ans=0x3f3f3f3f;
	for(i=0;i<=k;i++) ans=min(ans,dis[t+i*n]);//查询最短路
	cout<<ans<<endl;
	return 0;
}

计蒜客 A1958 Magical Girl Haze ↬\looparrowright

There are NN cities in the country, and MM directional roads from uu to vv(1≤u,v≤n)(1\le u, v\le n). Every road has a distance cic_i . Haze is a Magical Girl that lives in City 11, she can choose no more than KK roads and make their distances become 00. Now she wants to go to City NN, please help her calculate the minimum distance.

Input

The first line has one integer TT(1≤T≤5)(1 \le T\le 5), then following TT cases.
For each test case, the first line has three integers N,MN, M and KK.
Then the following MM lines each line has three integers, describe a road, Ui,Vi,CiU_i, V_i, C_i. There might be multiple edges between uu and vv.
It is guaranteed that N≤100000,M≤200000,K≤10,0≤Ci≤109N \le 100000, M \le 200000, K \le 10,0 \le C_i \le 10^9.
There is at least one path between City 11 and City NN.

Output

For each test case, print the minimum distance.

样例输入

1
5 6 1
1 2 2
1 3 4
2 4 3
3 4 1
3 5 6
4 5 2

样例输出

3

分析

与洛谷P4568几乎一样的套路，只是双向边变成了单向边。
注意多组输入和数据范围。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<queue>
#include<iostream>
#include<algorithm>
#include<cstdio>
#define N 100002
#define M 200006
#define K 22
using namespace std;
struct E
{
	int to;
	long long w;
	int Next;
}edge[M*K<<1];
int head[N*K],tot;
int n,m,k;
long long dis[N*K];
bool vis[N*K];
inline void add(int u,int v,long long w)
{
	tot++;
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].Next=head[u];
	head[u]=tot;
}
struct node
{
	int id;
	long long dis;
	bool operator<(const node &x)const
	{
		return x.dis<dis;
	}
};
void dijkstra()
{
	dis[1]=0;
	int i;
	priority_queue<node>q;
	q.push((node){1,0});
	while(!q.empty())
	{
		node now=q.top();
		q.pop();
		int x=now.id;
		if(vis[x]) continue;
		vis[x]=1;
		for(i=head[x];~i;i=edge[i].Next)
		{
			int y=edge[i].to;
			if(!vis[y]&&dis[y]>dis[x]+edge[i].w)
			{
				dis[y]=dis[x]+edge[i].w;
				q.push((node){y,dis[y]});
			}
		}
	}
}
void init()
{
	fill(head,head+3+n*(k+1),-1);
	tot=0;
	fill(vis,vis+3+n*(k+1),0);
	fill(dis,dis+n*(k+1)+3,1LL<<60);
}
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		scanf("%d%d%d",&n,&m,&k);
		int i;
		init();//多组输入初始化非常重要！
		while(m--)
		{
			int u,v;
			long long w;
			scanf("%d%d%lld",&u,&v,&w);
			add(u,v,w);
			for(i=1;i<=k;i++)
			{
				add(n*i+u,n*i+v,w);
				add(n*(i-1)+u,n*i+v,0);
			}
		}
		dijkstra();
		long long ans=1LL<<60;
		for(i=0;i<=k;i++) ans=min(ans,dis[(i+1)*n]);
		printf("%lld\n",ans);
	}
	return 0;
}

后记

本题为2018年 ACM-ICPC 南京网络赛 L 题，网络赛竟然能出原题，但是不能妄想次次做到原题 Orz\text{Orz}。

牛客竞赛 NC26257 小雨坐地铁 ↬\looparrowright

题目描述

小雨所在的城市一共有 mm 条地铁线，分别标号为 11 号线，22 号线 …… mm 号线。整个城市一共有 nn 个车站，编号为 1∼n1 \sim n 。其中坐 ii 号线需要花费 aia_i 的价格，每坐一站就需要多花费 bib_i 的价格。ii 号线有 cic_i 个车站，而且这 cic_i 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 ss 个车站坐地铁到第 tt 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 −1-1 。地铁是双向的，所以 ss 可能大于 tt。

输入描述

第一行输入四个正整数 n,m,s,tn,m,s,t，分别表示车站个数，地铁线数，起点站和终点站。
第二行到第 m+1m + 1 行，每行前三个数为 ai,bi,cia_i,b_i,c_i，分别表示坐 ii 号线的价格，ii 号线每坐一站多花的价格，ii 号线车站个数。接下来 cic_i 个数，表示 ii 号线的每一个车站的编号，单调递增。

输出描述

共一行，一个数表示最小花费，若不能到达输出 −1-1 。

示例1

输入
5 2 1 4
2 2 3 1 3 5
2 1 4 2 3 4 5
输出
7

说明

坐 11 号线，花费 22；
1→31 \rightarrow 3，花费 22；
换乘 22 号线，花费 22；
3→43 \rightarrow 4，花费 11；
所以最小总花费为 77 。

备注

1≤n≤103,1≤m≤500,1≤s,t≤n1 \leq n \leq 10^3, 1 \leq m \leq 500,1 \leq s,t \leq n
1≤ai,bi≤100,1≤ci≤n,∑i=1mci≤1051 \leq a_i,b_i \leq 100,1 \leq c_i \leq n,\sum\limits_{i = 1}^m c_i \leq 10^5

分析

分层图作为一种建图技巧，技巧性较强，此处的建图方式非常高明。
每条地铁线路可以看做一层图，对于第 ii 层图，只要建立第 ii 条地铁线即可。但是由于换乘站的情况存在，每层之间可能是相连的，如果处理每一层相连的点，就会显得相当麻烦。
对应每个车站，我们可以设立一个虚点。只要每层的车站与对应的虚点连接即可。那么分层图中，1∼m1\sim m 层是 mm 条地铁线，m+1m+1 层都是虚点，实点到虚点代价都是 00，虚点到实点代价是对应的 aia_i，这样就能起到换乘的效果。
设立虚点后，不用根据层与层间连边；否则这样每层都要连边，就要 m2nm^2n 条边；而设立虚点只要 2nm2nm 条边，大大降低了时间复杂度。同时也方便了计算，直接从 ss 的虚点到 tt 的虚点的最短路就是答案；如果不设虚点，要对应每个车站 ss 的地铁到每个车站 tt 的地铁求最短路。

如图，从 xx 到 yy 就是一个经过虚点换乘的过程。如果 xx 想通过换乘到达 zz，但是换乘后的地铁线路上显然没有 zz 这个站点，那么距离为无穷大，自然不是最短路；同样的， Dijkstra\text{Dijkstra} 算法的原理也不会产生一个点 xx 在其虚点和实点之间反复横跳的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 0x3f3f3f3f
#define N 1003
using namespace std;
struct E//链式前向星
{
	int to;
	int w;
	int Next;
}edge[N*N<<1];
int head[N*N],tot;
int dis[N*N];
bool vis[N*N];
int n,m,s,t;
inline void add(int u,int v,int w)//加边
{
	tot++;
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].Next=head[u];
	head[u]=tot;
}
/*-------------Dijkstra算法模板-------------*/
struct node
{
	int id;
	int dis;
	bool operator<(const node &x)const
	{
		return x.dis<dis;
	}
};
void dijkstra()
{
	dis[n*m+s]=0;
	int i;
	priority_queue<node>q;
	q.push((node){n*m+s,0});
	while(!q.empty())
	{
		node now=q.top();
		q.pop();
		int x=now.id;
		if(vis[x]) continue;
		vis[x]=1;
		for(i=head[x];~i;i=edge[i].Next)
		{
			int y=edge[i].to;
			if(!vis[y]&&dis[y]>dis[x]+edge[i].w)
			{
				dis[y]=dis[x]+edge[i].w;
				q.push((node){y,dis[y]});
			}
		}
	}
}
/*-----------=================------------*/
int main()
{
	memset(head,-1,sizeof(head));
	memset(dis,0x3f,sizeof(dis));
	cin>>n>>m>>s>>t;
	int i,j;
	for(i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		int now,last=-1;
		for(j=1;j<=c;j++)
		{
			scanf("%d",&now);
			if(~last)//至少读取了两个站点
			{
				//两个站点之间连边
				add((i-1)*n+now,(i-1)*n+last,b);
				add((i-1)*n+last,(i-1)*n+now,b);
			}
			last=now;//更新
			//连接虚点
			add((i-1)*n+now,n*m+now,0);
			add(n*m+now,(i-1)*n+now,a);
		}
	}
	dijkstra();
	if(dis[n*m+t]==inf) puts("-1");
	else cout<<dis[n*m+t]<<endl;//从虚点到虚点
	return 0;
}

后记

本题最早出现于牛客小白月赛 1616，后又在牛客算法周周练 33 中出现，还是很经典、很巧妙的一道题。