“自认为为他人好而做的事情并不一定是正确的。”，那是一篇充满了说教意味的故事。——《魔女之旅》

最短路

在 的路上又基本，又重要的，连 看到都会脸红的问题是哪个呢？

没错，就是最短路！（屑之路）

最短路问题，是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

最短之旅的开始

基本内容是：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。

很明显，上面这张图里，从 点到 点的最短路径是 ，最短距离是 。

最短路问题分为单源最短路和多源最短路。前者只需要求一个固定的起点到各个顶点的最短路径，后者则要求得出任意两个顶点之间的最短路径。

好，看完了这些我们来看看怎么解决最短路问题。

Floyd-Warshall

这是一个差劲的算法……算了，这是必要的牺牲，因为万事开头难（但似乎“万事开头难，然后中间难，最后结尾难”）。

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int dist[220][220];

void Floyd (int n)
{
	for (int k = 1; k <= n; k ++) // 对 n 个点进行遍历，这 n 个点是作为中间点 
	{
		for (int i = 1; i <= n; i ++) // 对 n 个起点进行遍历 
		{
			for (int j = 1; j <= n; j ++) // 对 n 个终点进行遍历 
			{
				dist[i][j] = min (dist[i][j], dist[i][k] + dist[k][j]); 
				// 比较原路径和我利用中间点的路径谁更短一点 
			}
		}
	} 
}

讲道理，这个方法比较像找中间商，如果我要买个东西，我需要考虑是直接从官网买呢，还是找中间商会便宜一点呢，通过这种方法来找最短路。

给出几张图来模拟一下

初始化是这样的：

我是一个标准的初始化

先是初始化，因为用的是邻接矩阵一般的存图方法， 中， 表示起点 的编号， 表示终点 的编号。

1
2
3
4
5
6
7
8
9
memset (dist, INF, sizeof (dist)); // 先将所有距离初始化为极大值 
for (int i = 1; i <= n; i ++)
	dist[i][i] = 0; // 自己到自己那肯定是 0 呀
for (int i = 1; i <= m; i ++)
{
	int u, v, w;
	scanf ("%d %d %d", &u, &v, &w);
	dist[u][v] = w; // 边权即距离 
}

然后是第一趟，当中间点为 时：

利用1号点进行松弛

此时当中间点为 时，没有任何一组点能通过 来缩短距离。

第二趟，中间点为 时：

利用2号点进行松弛

此时从 时， 走 会短亿些。

接下来是第三趟，当中间点为 时：

利用3号点进行松弛

虽然 也比 短，但是这条路径的最短距离已经被更新成 了，所以后面的过程都在考虑能否经由 点缩短 到 的距离。

时间复杂度是 ，有三重循环嘛，然后空间复杂度是 ， 可以说是比较差劲了，但是当解决单源最短路时，我们有更优的算法。

Bellman-Ford

铃男 河流浅水处（无端翻译）

这里我们先来了解一个神奇的名词松弛。

松弛操作

对边集合 中任意边，以 表示起点 到终点 边的权值，以 表示当前从起点 到顶点 的路径权值，

若存在 ，使得：

则更新 ：

松弛就是一种路径的更新（无非就是前面说的找中间商）

继续讲这个算法，因为起点被固定了，所以只需要一个一维数组 来记录每个点到终点的距离，初始化 ，其他为 ，方便松弛操作。

除了第一个点其他都初始化为INF

因为要找到最短路，所以我们要进行以下步骤：

1、松弛 ，此时 必然等于

2、再松弛 ，最短路的子路必然是最短路

3、再松弛 ，最终得到一条最短路……

那么看到以上步骤，我直接暴力枚举。

要做的就是把所有边松弛 遍。

1
2
3
4
5
6
7
8
9
10
void Bellman_Ford (int n, int m)
{
	while (n - 1 --)
	{
		for (int i = 1; i <= m; i ++) // 遍历边数 
		{
			dist[edges[i].to] = min (dist[edge[i].to], dist[edge[i].from] + dist[edge[i].w]); // 松弛 
		}
	}
}

来看一下过程：

暴力！！！

这里可以直接暴力存边集，因为这个算法不关心能连到哪条边。

时间复杂度是 。

而且这个 算法可以巧妙的考虑负权环的情况，只需再对所有边松弛一次，如果这次还有点被更新，就说明存在负权环。因为在正常情况下，最短路上的点是少于 个的，而存在负权环的时候，可以无数次的绕这个环，这样环上的点就是无限的（莫名喜感？）

SPFA

关于 ， 它死了

算法，也就是利用了队列优化的 算法，通过维护一个队列来降低时间复杂度。

可以观察到 算法第一次可能更新只能从源点 到达的点，然后下一次可能更新到这个点能到达的点， 算法就利用了这种算法。

一开始，先把源点放入队列：

常规操作

现在对于 号点，它能够到达 号点，于是 号点出队， 号点依次入队，入队时松弛相应的边（即从 共三条边）。

斩首了斩首了

现在队首是 号点了，于是 号点出队， 号点可以到达 号点，我们松弛 ，但是因为 号点已经在队列里了，所以不入队。

斩首斩首~

后面的流程就不多说了，接下来看看有 个点的情况：

表现一下 $SPFA$ 的优越性

流程与前面相同，到了 号点，它能到达 ，于是我们进行松弛。

常规斩首操作

然后到达 号点的距离变短了，而到达 号点的最短距离目前为止还是那么长（人家才刚进来，不要欺负萌新好嘛）

接下来 号点是队头，但是没能更新什么东西，因为虽然它能到达 号点，但是 号点的最短距离是 ，不能更新。

3号点好菜

接下来是 号点，最后一次能到达 号点的机会，成功地把答案更新到了 。

流向改变了！

显然因为我们只更新这个点能到达的点，所以我们就省去了松弛其他无关紧要的边的时间，而且也不会松弛已经松弛过的边，目的只有得到从源点到终点的最短路，所以就快了很多（据说随机数据下期望时间复杂度是 ）

总结一下， 算法是怎么“只更新需要更新的点”的：

  1. 只让当前点能到达的点入队
  2. 如果一个点已经入队，不重复入队
  3. 如果一条边还未更新到，它的终点肯定不入队

原理是，我们的目的是先松弛一个点和所有它的终点连接的边，将这些能到达的点加入队列，然后重复这个操作，如果有别的点能到达这个点，那说明这个前者肯定已经入过队了，那么利用三角形原理松弛这条边。

我们用一个 数组来记录一个点是否在队列中，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void SPFA (int s) // 这里 s 表示源点 
{
	queue<int> Q;
	Q.push (s); // 将源点推入队列 
	while (!q.empty ()) // 如果队列不为空，等价于 q.size () != 0
	{
		int p = Q.front (); // 获取队头（斩首） 
		Q.pop (); // 老规矩，如果已经得到队头了就要删掉（你可以变相理解吃掉这个头）
		inqueue[p] = 0; // 记录，此点被踹出队列了 
		for (int i = head[p]; i; i = edge[i].nxt) // 前向星是我们的好朋友
		{
			int to = edge[i].to; // 获取终点
			if (dist[to] > dist[p] + edge[i].w) // 如果此时可被松弛，即满足三角形定理
			{
				dist[to] = dist[p] + edge[i].w; // 改旗易帜！！！
				if (!inqueue[to]) // 如果此时这个终点未入过队 
				{
					inqueue[to] = 1; // 新成员！！！
					q.push (to); //  热烈欢迎！！！ 
				}
			} 
		} 
	} 
}

但是它的时间复杂度极不稳定，最坏情况下可能被卡成 ，也就是 ，但也不妨碍它成为一种常用算法。

也可以判负权环，不过需要记录下每个点进入队列的次数，当一个点入队次数超过 次，就认为是出现了负权环。

Djikstra

这种算法，不妨叫它 算法 wwwwwwwww（原因详见 nottttttthy的一篇题解 ）

说点正经的，这是一个复杂度稳定的算法。

基于一种贪心的思想，现在假定一张没有负权的图。首先，起点到起点的距离是 。现在我们对起点和它能直接到达的点进行松弛。

Djikstra = Saber-Xuhf

因为没有负边，所以我们可以肯定，离起点最近的那个顶点的 一定已经是最终结果，为什么？显然因为不可能经由其他点，使该起点到该点的距离变得更远。

那现在来看 号点：

贪，就硬贪

我们对 号点和它能到达的点进行松弛。此时 保存的是起点直接到达或经由 号点到达每个点的最短距离。我们这时候取出未访问过的 最小的点（即 号点），那么这个点的 也不可能变得再短了（因为其他路径至少都要从起点直接到达、或者经由 号点到达另一个点，再从这个点到达 号点）

继续这个操作，现在我们对 号点下手：

4号点惨遭不幸

然后分别去看 号点和 号点，直到所有点都被考察过。

总结一下， 的过程就是不断取出离起点最近而没有被访问过的点，然后松弛所有它和它能到达的所有点。

如何取出这个点？如果暴力寻找，那就是朴素的 算法，时间复杂度是 。但我们可以使用堆优化。具体而言，就是使用一个优先队列（或者手写堆）来维护所有节点。这样可以实现在 的时间内跑完最短路。

首先写一个结构体：

1
2
3
4
struct Polar {
	int dist, id; // 存距离和编号
	Polar (int dist, int id) : dist (dist), id (id) {}
};

然后写一个仿函数（也可以重载 的小写运算符代替），再构建优先队列。

1
2
3
4
5
6
struct cmp {
	bool operator () (Polar a, Polar b){ // 重载运算符，使其成为一个仿函数 
		return a.dist > b.dist; // 这里是大于，使得距离短的先出队 
	}
};
priority_queue <Polar, vector <Polar>, cmp> Q; // 构建优先队列

来看 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Djikstra (int s)
{
	memset (dist, inf, sizeof (dist));
	dist[0] = 0;
	Q.push (Polar (0, s));
	while (!Q.empty ()) // 队列非空，等价于 Q.size () != 0
	{
		int p = Q.top ().id; // 斩首
		Q.pop (); // 吃掉这个头
		if (vis[p]) // 看来是已经被访问过了
			continue;
		vis[p] = 1; // 标记为访问过
		for (int i = head[p]; i; i = edge[i].nxt) // 前向星遍历 
		{
			int to = edge[i].to; // 获取队头 
			dist[to] = min (dist[to], dist[p] + edge[i].w); // 松弛这条边 
			if (!vis[to]) // 即未被访问且距离最短的点，因为我们已经使用优先队列优化了） 
				Q.push (Polar (dist[to], to)); // 就将这个点推入队列 
		} 
	} 
}

显然，我们也可以用 里的 ：

1
2
typedef pair <int, int> Pair;
priority_queue <Pair, vector<Pair>, greater<Pair> > Q; // greater就是从大到小排列

这样的代码与之前只有三行的区别：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Djikstra (int s)
{
	memset (dist, inf, sizeof (dist));
	dist[s] = 0;
	Q.push (make_pair (0, s)); // 推入队列 
	while (!Q.empty ()) // 队列非空，等价于 Q.size () != 0 
	{
		int p = Q.top ().second; // 就是 pair 里的第二关键字，点的编号
		Q.pop (); // 老规矩，斩首
		if (vis[p]) // 保证没被访问过 
			continue; 
		vis[p] = 1; // 标记被访问
		for (int i = head[p]; i; i = edge[i].nxt) // 前向星遍历 
		{
			int to = edge[i].to; // 获取终点
			dist[to] = min (dist[to], dist[p] + edge[i].w); // 松弛 
			if (!vis[to]) // 如果未被访问过 
				Q.push (make_pair (dist[to], to)); // 就将这个当前距离最短的点推入队列 
		}
	} 
}

路径打印

对于这种简单的任务，我们只需要一个数组 来记录前驱就可以了，每当更新一个节点的最短路径时，同时更新它的前驱，只要在松弛中加入一行：

1
pre[to] = p;

然后在最后输出一整坨路径就可以了（量词爆炸！）。

最短路树

这个东西感觉和最短路没啥关系但是因为看着像 所以我就拉上来讲了（主要是因为之前没学到）。

用一道板子题来开始这个话题：

Shortcut G

每天晚上， 都会敲响一个巨大的铃铛，召唤奶牛来牛棚享用晚餐，所有奶牛都会沿着最短的路径行走，有 块草地，牛棚位于草地 。草地之间由 条小路连接，每条小路都有通过时间，从每块草地出发都存在由一些小路组成的路径能到达牛棚。

每块草地中有一些奶牛，如果它们发现有多条路径消耗时间一样少，它们会选择字典序较小的那一条。

担心牛棚距离某些草地太远，他计算了每条奶牛消耗的时间相加，以这个和为总移动时间。所以他现在想凭空变出一条从牛棚连接到某块其他的草地用时为 的近道，来尽可能地减少总移动时间，求这条路径

要做的操作就是从节点 开始做最短路，建出最短路树，然后跑 。 对最短路树上的一点 ，其子树中的点在回家的过程中都会经过该点。此时若连接一条从该节点到 号节点的边，则其最短路长度总和会变成 。

代码如下：

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 1;

struct Edge {
	int nxt, to, w;
} edge[N * 20];

struct Node {
	int id, val;
	bool operator < (Node x) const {
		return val > x.val;
	}
};

int head[N], cnt;
int n, m, t, c[N];
int dist[N], siz[N], ans;
bool vis[N], f[N];
priority_queue <Node> Q; 
vector <int> G[N / 10];

inline void add_edge (int u, int v, int w)
{
	edge[++ cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

void dijkstra (int s)
{
	Q.push ({1, 0});
	while (!Q.empty ())
	{
		Node p = Q.top ();
		Q.pop ();
		if (vis[p.id])
			continue;
		vis[p.id] = 1;
		dist[p.id] = p.val;
		for (int i = head[p.id]; i; i = edge[i].nxt)
			Q.push ({edge[i].to, p.val + edge[i].w});
	}
}

void dfs (int p)
{
	siz[p] = c[p];
	f[p] = 1;
	for (vector <int> :: iterator it = G[p].begin (); it != G[p].end (); it ++)
		if (!f[*it])
		{
			dfs (*it);
			siz[p] += siz[*it];
		}
	ans = max (ans, siz[p] * (dist[p] - t));
}

signed main ()
{
	int x, y, z;
	scanf ("%lld %lld %lld", &n, &m, &t);
	for (int i = 1; i <= n; i ++)
		scanf ("%lld", &c[i]);
	for (int i = 1; i <= m; i ++)
	{
		scanf ("%lld %lld %lld", &x, &y, &z);
		add_edge (x, y, z);
		add_edge (y, x, z); 
	}
	dijkstra (1);
	memset (vis, 0, sizeof vis);
	for (int i = 1; i <= n; i ++)
		for (int j = head[i]; j; j = edge[j].nxt)
			if (dist[edge[j].to] == dist[i] + edge[j].w && !vis[edge[j].to])
			{
				vis[edge[j].to] = 1;
				G[i].push_back (edge[j].to);
				G[edge[j].to].push_back (i);
			}
	dfs (1);
	printf ("%lld\n", ans);
}

Johnson

算法用于解决全源最短路问题，这种问题通常不常见但是一出现就是巅峰。

因为数据会出现负环，会卡 ，数据会很大，前面的老家伙们就都干不掉了，所以出现了这种算法，还有就是，这个算法的需要您掌握前面的最短路算法。

任意两点之间的最短路可以通过跑 次 解决，时间复杂度是 ，用 是 ，但是我们发现跑 次在有堆优化加成的 时，速度会更快。

但是有负环。

那你可能就会想到给所有边加上一个更大的正数，可惜这已经不是最短路了，不然将绝杀。

而这里我们使用一个编号为 的虚点，从这个点向其他点连一条边权为 的边。

接下来用 求出从 号点到其他所有点的最短路，记为 。

假如存在一条从 点到 点，边权为 的边，将这条边的边权设为 。

这里先鸽了，暑假找个机会补起来。