最短路 Shortest Path

4 个算法
4 Algorithms

  1. Bellman Ford
  2. Dijkstra
  3. Floyd
  4. SPFA

https://www.luogu.com.cn/problem/P2176

P1339 [USACO09OCT]Heat Wave G
P5837 [USACO19DEC]Milk Pumping G
P3659 [USACO17FEB]Why Did the Cow Cross the Road I G
P6145 [USACO20FEB]Timeline G
P1339 [USACO09OCT]Heat Wave G
P1821 [USACO07FEB]Silver Cow Party S
P2865 [USACO06NOV]Roadblocks G

CF938D Buy a Ticket
CF666B World Tour
CF986A Fair

图的存储

前向星链表 或 vector
参考单独页面 图的存储

基本性质

对于无向图来说，从点S到点T的最短路长度 一定等于 从点T到点S的最短路长度
对于有向图来说，从点S到点T的最短路长度 一定等于 所有边反向之后从点T到点S的最短路长度

做一次Dijkstra 可以求出起点到所有点的最短路
如果需要求所有点到某个终点的最短路，可以把边反向，把终点当做起点，再求最短路

如果S到T的最短路是 S -> A -> B -> ... -> C -> D -> T
那么对于中间的任何一个点，路径的前缀就是到他的最短路
不可能发生S到T是最短路，但是S到最短路上某个点，有更短的方案

Bellman Ford

对于一条从uu到vv长度为ww的边，最终的最短路一定满足dv≤du+wd_v \leq d_u + w否则dvd_v还可以被更新为du=wd_u = w，这也叫做松弛操作。

循环nn次，对每条边进行松弛操作，便可以得到每个点的最短路。

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        d[v[i]] = min(d[v[i]], d[u[i]] + w[i]);
    }
}

特别的，如果第nn轮更新（即i=n−1i = n - 1时）发生了松弛操作，那么说明某个点的最短路上存在nn条边，这是不可能的，一定有负环的存在。

Bellman Ford

https://en.wikipedia.org/wiki/Bellman–Ford_algorithm

Time O(nm)
时间复杂度 O(nm)

Relax Operation
松弛操作

if (dist[edge_end] > dist[edge_start] + edge_length)
{
    dist[edge_end] = dist[edge_start] + edge_length;
}

如果一条边终点的距离 大于 起点的距离 加 边的长度
把终点的距离 改成 起点的距离 加 边的长度

n is the number of vertices.
如果 n 是图的点数

There are at most n-1 edges on the shortest path.
那么最短路上至多有 n-1 条边

如果最短路上有n条边
就意味着某个点到过2次
就意味着出环了（长度为0的环或者长度为负数的环）

for (int i = 0; i < n; i++) // n-1 times 循环 n-1 次
{
    bool changed = false;
    for (int j = 0; j < m; j++) // all edges 枚举所有的边
    {
        // Relax Operation 松弛操作
        if (dist[end[j]] > dist[start[j]] + length[j])
        {
            dist[end[j]] = dist[start[j]] + length[j];
            changed = true;
        }
    }
    // 如果枚举所有的边，没有进行松弛操作，那么退出
    if (!changed)
    {
        break;
    }
}

P1938 [USACO09NOV]Job Hunt S

d[i] largest income ending at vertex i.

if (dist[edge_end] < dist[edge_start] + edge_length)
{
    dist[edge_end] = dist[edge_start] + edge_length;
}

如果最短路上有n条边，那么这个图中有负环
If there are n edges on the shortest path, then there is a negative-weight cycle.
USACO Heat Wave

Dijkstra

基于贪心的思想，不能处理负权的情况，每个点额外维护一个属性，表示是否确定了最短路。

每次找到距离最短，不确定最短路的点，标记为确定了最短路，用于更新其他节点。

d[s] = 0;
for (int i = 0; i < n; i++) {
    int t = -1;
    for (int j = 0; j < n; j++) {
        if (!v[j]) {
            if (t == -1 || d[j] < d[t]) {
                t = j;
            }
        }
    }
    v[t] = 1;
    for (each edge e of t) {
        relax(e);
    }
}

这个算法可以被堆或者线段树优化，理论最优的做法是用Fibonacci堆，但是效果一般。
但是在实际实现中，往往不标记，实现成优先队列优化的SPFA。

Dijkstra

用来求最短路
Dijkstra can not deal with negative edges.
Dijkstra 不能处理负权最短路

use set or priority_queue to optimize Bellman Ford
相当于用 set 或者 priority_queue 来优化 Bellman Ford

The algorithm we used, is not exactly the same as the algorithm in the paper.
这个算法实际实现出来，并不和论文上的算法一模一样

priority_queue, we can only delete the top
priority_queue 只能删除最大值

set, we can delete anything we want
set 可以删除任意值（相当于支持修改）

https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P4779.cpp

in C++
by default, priority_queue top is the largest one.
默认，C++中的 priority_queue 的 top 是最大的

Traditional Version
论文上的实现方法

for (int i = 0; i < n; i++) // 循环n次
{
// find a unvisited vectex with the minimum distance
找到一个 距离最小 未标记的点

标记上他

更新所有他能到的点的距离
update all its neighbors

}

时间复杂度 O(m log n)
Time: O(m log n)

#include <bits/stdc++.h>
using namespace std;
int n, m, s;
vector<pair<int, int> > a[100020];
priority_queue<pair<int, int> > q;
int d[100020];
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(make_pair(y, z));
    }
    memset(d, 0x3f, sizeof d); // d[i] = 0x3f3f3f3f;
    // 
    d[s] = 0;
    q.push(make_pair(-d[s], s)); // q.top() is the largest
    while (q.size() > 0) {
        pair<int, int> u = q.top();
        q.pop();
        if (-u.first != d[u.second]) {
        // if u is not the newest
        // what happens if do not continue
            continue;
        }
        // if there is no negative edges.
        // for every u.second, we do it once.
        for (int i = 0; i < a[u.second].size(); i++) {
            pair<int, int> e = a[u.second][i]; // in total m times.
            if (d[e.first] > d[u.second] + e.second) {
                d[e.first] = d[u.second] + e.second;
                q.push(make_pair(-d[e.first], e.first)); // log n
                // push the new version
                // do not delete the old version
                // priority queue does not support deletion.
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", d[i], i == n ? '\n' : ' ');
    }
    return 0;
}

参考题目

spoj ADRABR

P5201 [USACO19JAN]Shortcut G

https://www.luogu.com.cn/problem/P5201

题目背景

USACO 19年一月月赛金组第三题

题目描述

每天晚上，Farmer John都会敲响一个巨大的铃铛，召唤他的奶牛们前来牛棚享用晚餐。奶牛们都急切地想要前往牛棚，所以她们都会沿着最短的路径行走。
农场可以描述为N块草地（1≤N≤10,000），方便起见编号为1…N，牛棚位于草地1。草地之间由M条双向的小路连接（N-1≤M≤50,000）。每条小路有其通过时间，从每块草地出发都存在一条由一些小路组成的路径可以到达牛棚。

草地i中有ci头奶牛。当她们听到晚餐铃时，这些奶牛都沿着一条消耗最少时间的路径前往牛棚。如果有多条路径并列消耗时间最少，奶牛们会选择其中“字典序”最小的路径（也就是说，她们通过在两条路径第一次出现分支的位置优先选择经过编号较小的草地的方式来打破并列关系，所以经过草地7、3、6、1的路径会优先于经过7、5、1的路径，如果它们所消耗的时间相同）。

Farmer John担心牛棚距离某些草地太远。他计算了每头奶牛路上的时间，将所有奶牛消耗的时间相加，称这个和为总移动时间。他想要通过额外添加一条从牛棚（草地1）连接到某块他选择的其他草地的、通过时间为T（1≤T≤10,000）的“近道”来尽可能地减少总移动时间。当一头奶牛在她平时前往牛棚的路上偶然看见这条近道时，如果这条近道能够使她更快地到达牛棚，她就会走这条路。否则，一头奶牛会仍然沿着原来的路径行走，即使使用这条近道可能会减少她的移动时间。

请帮助Farmer John求出通过添加一条近道能够达到的总移动时间减少量的最大值。

输入格式

输入的第一行包含N、M和T。以下N行包含c1…cN，均为0…10,000范围内的整数。以下M行，每行由三个整数a，b和t描述了一条小路，这条小路连接了草地a和b，通过时间为t。所有的通过时间在1…25,000范围内。

输出格式

输出Farmer John可以达到的总移动时间的最大减少量。

样例 #1

样例输入 #1
5 6 2
1 2 3 4 5
1 2 5
1 3 3
2 4 3
3 4 5
4 5 2
3 5 7
样例输出 #1
40

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > a[10020];
int n, m, t;
int c[10020];
int d[10020];
int f[10020];
set<pair<int, int> > s;
vector<int> q;
int main() {
	scanf("%d%d%d", &n, &m, &t);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
	}
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(make_pair(y, z));
		a[y].push_back(make_pair(x, z));
	}
	memset(d, 0x3f, sizeof d);
	d[1] = 0;
	s.insert(make_pair(d[1], 1));
	while (s.size()) {
		int u = s.begin() -> second;
		q.push_back(u);
		s.erase(s.begin());
		for (int i = 0; i < a[u].size(); i++) {
			if (d[a[u][i].first] > d[u] + a[u][i].second) {
				s.erase(make_pair(d[a[u][i].first], a[u][i].first));
				d[a[u][i].first] = d[u] + a[u][i].second;
				f[a[u][i].first] = u;
				s.insert(make_pair(d[a[u][i].first], a[u][i].first));
			} else if (d[a[u][i].first] == d[u] + a[u][i].second) {
				f[a[u][i].first] = min(f[a[u][i].first], u);
			}
		}
	}
	long long ans = 0;
	for (int i = q.size() - 1; i > 0; i--) {
		ans = max(ans, (long long)c[q[i]] * (d[q[i]] - t));
		c[f[q[i]]] += c[q[i]];
	}
	printf("%lld\n", ans);
	return 0;
}

题解

http://usaco.org/index.php?page=viewproblem2&cpid=899
shortest path tree
最短路树

P5122 [USACO18DEC]Fine Dining G

https://www.luogu.com.cn/problem/P5122

题目背景

题目描述

漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。

农场由 NN 片牧场组成（2≤N≤5×1042\le N\le 5\times 10^4），方便起见编号为 1…N1\dots N。所有奶牛都要前往位于牧场 NN 的牛棚。其他 N−1N-1 片牧场中每片有一头奶牛。奶牛们可以通过 MM 条无向的小路在牧场之间移动（1≤M≤1051\le M\le 10^5）。第i条小路连接牧场 aia_i 和 bib_i，通过需要时间 tit_i。每头奶牛都可以经过一些小路回到牛棚。

由于饥饿，奶牛们很乐于在他们回家的路上停留一段时间觅食。农场里有 KK 个有美味的干草捆，第 ii 个干草捆的美味值为 yiy_i。每头奶牛都想要在她回牛棚的路上在某一个干草捆处停留，但是她这样做仅当经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值。注意一头奶牛仅仅“正式地”在一个干草捆处因进食而停留，即使她的路径上经过其他放有干草捆的牧场；她会简单地无视其他的干草捆。

输入格式

输入的第一行包含三个空格分隔的整数 NN，MM 和 KK。以下 MM 行每行包含三个整数 aia_i，bib_i 和 tit_i，表示牧场 aia_i 和 bib_i 之间有一条需要 tit_i 时间通过的小路（aia_i 不等于 bib_i，tit_i 为不超过 10410^4 的正整数）。

以下 KK 行，每行以两个整数描述了一个干草捆：该干草捆所在牧场的编号，以及它的美味值（一个不超过 10910^9 的正整数）。同一片牧场中可能会有多个干草捆。

输出格式

输出包含 N−1N-1 行。如果牧场 ii 里的奶牛可以在回牛棚的路上前往某一个干草捆并且在此进食，则第 ii 行为一个整数 11，否则为一个整数 00。

样例 #1

样例输入 #1
4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7
样例输出 #1
1
1
1

提示

在这个例子中，牧场 33 里的奶牛可以停留进食，因为她回去的时间仅会增加 66（从 22 增加到 88），而这个增加量并没有超过干草捆的美味值 77。牧场 22 里的奶牛显然可以吃掉牧场 22 里的干草，因为这并不会导致她的最佳路径发生变化。对于牧场 11 里的奶牛是一个有趣的情况，因为看起来她的最佳路径（1010）可能会因为前去进食而有过大的增加量。然而，确实存在一条路径使得她可以前去干草捆处停留：先到牧场 44，然后去牧场 22（吃草），然后回到牧场 44。

参考代码

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > a[50020];
int n, m, k;
int d1[50020];
int d2[50020];
set<pair<int, int> > s;
void dijk(int *d) {
	for (int i = 1; i <= n; i++) {
		s.insert(make_pair(d[i], i));
	}
	while (s.size()) {
		int u = s.begin() -> second;
		s.erase(s.begin());
		for (int i = 0; i < a[u].size(); i++) {
			if (d[a[u][i].first] > d[u] + a[u][i].second) {
				s.erase(make_pair(d[a[u][i].first], a[u][i].first));
				d[a[u][i].first] = d[u] + a[u][i].second;
				s.insert(make_pair(d[a[u][i].first], a[u][i].first));
			}
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(make_pair(y, z));
		a[y].push_back(make_pair(x, z));
	}
	memset(d1, 0x3f, sizeof d1);
	d1[n] = 0;
	dijk(d1);
	memset(d2, 0x3f, sizeof d2);
	for (int i = 0; i < k; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		d2[x] = d1[x] - y;
	}
	dijk(d2);
	for (int i = 1; i < n; i++) {
		printf("%d\n", d1[i] >= d2[i]);
	}
}

题解

http://usaco.org/index.php?page=viewproblem2&cpid=861
Shortest path with multi starting vertices (and different starting distance).
haybale

P1629 邮递员送信

https://www.luogu.com.cn/problem/P1629

题目背景

题目描述

有一个邮递员要送东西，邮局在节点 11。他总共要送 n−1n-1 样东西，其目的地分别是节点 22 到节点 nn。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 mm 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n−1n-1 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数，nn 和 mm，表示城市的节点数量和道路数量。

第二行到第 (m+1)(m+1) 行，每行三个整数，u,v,wu,v,w，表示从 uu 到 vv 有一条通过时间为 ww 的道路。

输出格式

输出仅一行，包含一个整数，为最少需要的时间。

样例 #1

样例输入 #1
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2
样例输出 #1
83

提示

对于 30%30\% 的数据，1≤n≤2001 \leq n \leq 200。

对于 100%100\% 的数据，1≤n≤1031 \leq n \leq 10^3，1≤m≤1051 \leq m \leq 10^5，1≤u,v≤n1\leq u,v \leq n，1≤w≤1041 \leq w \leq 10^4，输入保证任意两点都能互相到达。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
vector<pair<int, int> > a[100020];
vector<pair<int, int> > b[100020];
priority_queue<pair<int, int> > q;
int d[100020];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(make_pair(y, z));
		b[y].push_back(make_pair(x, z));
	}
	memset(d, 0x3f, sizeof d);
	d[1] = 0;
	q.push(make_pair(-d[1], 1));
	while (q.size() > 0) {
		pair<int, int> u = q.top();
		q.pop();
		if (-u.first > d[u.second]) {
			continue;
		}
		for (int i = 0; i < a[u.second].size(); i++) {
			pair<int, int> e = a[u.second][i];
			if (d[e.first] > d[u.second] + e.second) {
				d[e.first] = d[u.second] + e.second;
				q.push(make_pair(-d[e.first], e.first));
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		ans += d[i];
	}
	memset(d, 0x3f, sizeof d);
	d[1] = 0;
	q.push(make_pair(-d[1], 1));
	while (q.size() > 0) {
		pair<int, int> u = q.top();
		q.pop();
		if (-u.first > d[u.second]) {
			continue;
		}
		for (int i = 0; i < b[u.second].size(); i++) {
			pair<int, int> e = b[u.second][i];
			if (d[e.first] > d[u.second] + e.second) {
				d[e.first] = d[u.second] + e.second;
				q.push(make_pair(-d[e.first], e.first));
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		ans += d[i];
	}
	printf("%d\n", ans);
	return 0;
}

题解

P4779 【模板】单源最短路径（标准版）

https://www.luogu.com.cn/problem/P4779

题目背景

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

100→60100 \rightarrow 60；

Ag→Cu\text{Ag} \rightarrow \text{Cu}；

最终，他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

题目描述

给定一个 nn 个点，mm 条有向边的带非负权图，请你计算从 ss 出发，到每个点的距离。

数据保证你能从 ss 出发到任意点。

输入格式

第一行为三个正整数 n,m,sn, m, s。
第二行起 mm 行，每行三个非负整数 ui,vi,wiu_i, v_i, w_i，表示从 uiu_i 到 viv_i 有一条权值为 wiw_i 的有向边。

输出格式

输出一行 nn 个空格分隔的非负整数，表示 ss 到每个点的距离。

样例 #1

样例输入 #1
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
样例输出 #1
0 2 4 3

提示

样例解释请参考 数据随机的模板题。

1≤n≤1051 \leq n \leq 10^5；

1≤m≤2×1051 \leq m \leq 2\times 10^5；

s=1s = 1；

1≤ui,vi≤n1 \leq u_i, v_i\leq n；

0≤wi≤1090 \leq w_i \leq 10 ^ 9,

0≤∑wi≤1090 \leq \sum w_i \leq 10 ^ 9。

本题数据可能会持续更新，但不会重测，望周知。

2018.09.04 数据更新 from @zzq

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, s;
vector<pair<int, int> > a[100020];
priority_queue<pair<int, int> > q;
int d[100020];
int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(make_pair(y, z));
	}
	memset(d, 0x3f, sizeof d);
	d[s] = 0;
	q.push(make_pair(-d[s], s));
	while (q.size() > 0) {
		pair<int, int> u = q.top();
		q.pop();
		if (-u.first > d[u.second]) {
			continue;
		}
		for (int i = 0; i < a[u.second].size(); i++) {
			pair<int, int> e = a[u.second][i];
			if (d[e.first] > d[u.second] + e.second) {
				d[e.first] = d[u.second] + e.second;
				q.push(make_pair(-d[e.first], e.first));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%d%c", d[i], i == n ? '\n' : ' ');
	}
	return 0;
}

题解

bzoj 3040

http://www.lydsy.com/JudgeOnline/problem.php?id=3040
斐波那契堆 优化 Dijkstra
Fibonacci Heap

  1. Fast Read
    读入优化
    scanf and cin are slow
    getchar() / fread

  2. Ignore the generated edges.
    忽略生成的边

  3. Reverse all edges.
    所有边反向

Floyd

本质思路是动态规划，用f[k][i][j]表示除了起点和终点，只允许经过标号小于等于k的节点，从i到j的最短路。
初始f[0][i][j]取决于i到j的最短边。
转移方程

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j])
        }
    }
}

实际上第一维可以省略

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            f[i][j] = min(f[i][j], f[i][k]+f[k][j])
        }
    }
}

不要记错循环的顺序，先枚举中间点。
Floyd还可以用于计算传递闭包和无向图最小环，是一个值得记住的算法。

Floyd

find the shortest paths between all pairs of vertices
任意两点之间的最短路

n times dijkstra O(m log n) * n
做n次 dijkstra 时间复杂度是 O(m log n) * n

floyd time complexity O(n^3)
floyd 时间复杂度是 O(n^3)

if m>=n2/log⁡nm >= n^2 / \log n, then floyd is faster.
如果边数超过 m>=n2/log⁡nm >= n^2 / \log n 那么 floyd 更快

所以 Floyd 适合在完全图上使用

完全图：任意两个点之间都有边

https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm

Dynamic Programming
动态规划的思路

d[i][j][k] means from i to j, we can only use intermediate vertices <= k,
the length the shortest path
d[i][j][k] 表示 从 i 到 j 除了起点和终点之外，只能经过标号 <= k 的点

d[i][j][0] input graph
d[i][j][0] 输入的图，不能经过任何中间点

d[i][j][n] output
d[i][j][n] 输出的图，可以经过任何中间点

d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

读入 邻接矩阵
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        cin >> d[i][j];
    }
}

读入边
for (int i = 0; i < m; i++)
{
    cin >> x >> y >> z;
    d[x][y] = min(d[x][y], z);
    // multi edges
    // 可能有重边
}

// first we must enumerate the intermediate vertex
// 首先枚举中间点 k
for (int k = 0; k < n; k++) 
{
    // 枚举起点i
    for (int i = 0; i < n; i++)
    {
        // 枚举终点j
        for (int j = 0; j < n; j++)
        {
            // we can swap loop i and loop j
            // i 和 j 的循环可以交换
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            // d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])
            // optimize to 2D array
            // 实际实现中并不会用三维数组，会用二维数组
        }
    }
}

P2910 [USACO08OPEN]Clear And Present Danger S

https://www.luogu.com.cn/problem/P2910

#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[10020];
int d[120][120];
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> d[i][j];
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for (int i = 1; i < m; i++) {
        ans += d[a[i - 1]][a[i]];
    }
    cout << ans << endl;
}

CF25C

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z;
int d[320][320];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> d[i][j];
		}
	}
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	cin >> m;
	for (int k = 0; k < m; k++)
	{
		cin >> x >> y >> z;
		d[x][y] = min(d[x][y], z);
		d[y][x] = min(d[y][x], z);
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				d[i][j] = min(d[i][j], d[i][x] + d[x][j]);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				d[i][j] = min(d[i][j], d[i][y] + d[y][j]);
			}
		}
		long long z = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j < i; j++)
			{
				z += d[i][j];
			}
		}
		cout << z << " ";
	}
	return 0;
}

Floyd算法的应用

Applications

  1. The shortest simple cycle in undirected graph.
  2. 无向图最小环

P6175 无向图的最小环问题

最小环上至少三个点，并且不能有重复的点（当然也没有重复的边）
枚举k点 是最小环中标号最大的的节点
k is largest vertex in the cycle
(u --- k --- v --- .... --- u)

假设 k 两边点是 u 和 v
那么从 v 到 u 找一条只允许只用标号 <= k-1 的最短路

u到k的边 k到v的边 v到u的路径 构成一个环，用这个环更新答案
use a[u][k] + a[k][v] + d[v][u][k-1] to update the answer

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[120][120];
int d[120][120];
int main() {
    cin >> n >> m;
    memset(a, 0x1f, sizeof a);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        a[x][y] = min(a[x][y], z);
        a[y][x] = min(a[y][x], z);
    }
    int ans = 0x1f1f1f1f;
    memcpy(d, a, sizeof d);
    for (int k = 1; k <= n; k++) {
        // 环上最大的点是k，和k相邻的两个点是i和j
        for (int i = 1; i < k; i++) {
            for (int j = 1; j < i; j++) {
                ans = min(ans, a[i][k] + a[k][j] + d[i][j]);
                // d[i][j]存的最短路是 从i到j，只能经过标号<k的点的最短路
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    // 如果找不到有意义的答案就是无解
    if (ans == 0x1f1f1f1f) {
        printf("No solution.\n");
    } else {
        printf("%d\n", ans);
    }
    return 0;
}

P1119 灾后重建

https://www.luogu.com.cn/problem/P1119

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int t[220];
int d[220][220];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &t[i]);
    }
    memset(d, 0x3f, sizeof d);
    for (int i = 0; i < n; i++)
    {
        d[i][i] = 0;
    }
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        d[x][y] = z;
        d[y][x] = z;
    }
    scanf("%d", &q);
    for (int l = 0, k = 0; l < q; l++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        for (; k < n && t[k] <= z; k++)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        if (t[x] <= z && t[y] <= z && d[x][y] < 0x3f3f3f3f)
        {
            printf("%d\n", d[x][y]);
        }
        else
        {
            printf("%d\n", -1);
        }
    }
    return 0;
}

用 bitset 做传递闭包 use bitset to maintain

P4306 [JSOI2010]连通数

https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P4306.cpp

P4306 [JSOI2010]连通数
if we can from i to j
如果可以从i到j
d[i][j] = 1
否则
d[i][j] = 0

读入n行n列的01矩阵
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        scanf("%1d", &d[i][j]);
    }
    d[i][i] = 1; // 自己到自己一定可以
}

直接传递闭包
for (int k = 0; k < n; k++)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (d[i][k] && d[k][j])
            {
                d[i][j] = 1;
            }
        }
    }
}

可以调整 if 的顺序
for (int k = 0; k < n; k++)
{
    for (int i = 0; i < n; i++)
    {
        if (d[i][k] == 1)
        {
            for (int j = 0; j < n; j++)
            {
                d[i][j] |= d[k][j];
            }
        }
    }
}

bitset<2000> d[2000];
for (int k = 0; k < n; k++)
{
    for (int i = 0; i < n; i++)
    {
        if (d[i][k] == 1)
        {
            d[i] |= d[k];
        }
    }
}

最后数一下 d 里面有多少个 1
count how many 1s in d[][]

bitset 有函数 count 数有多少个 1

SPFA

队列优化版的Bellman Ford

基本没什么用的算法

SPFA (Only in China, useless)

use queue to optimize Bellman Ford

If there are negative edges
The time complexity is very hard to estimate.

SPFA

SPFA一般只用于费用流和判断负环，没有负环尽量使用SPFA。

其中判断负环的又分为几种情况。

  1. 从起点到终点的路上有负环，最短路为负无穷。
  2. 从起点可以到负环，但是一旦进入负环便无法到达终点，所以最短路存在。
  3. 存在负环，但是从起点无法到达。

其他变形

可能需要求解

  1. 最长路。把所有边取相反数即可
  2. 乘积最大。边权相乘，可以通过取对数转化为加法。

参考题目

Luogu P3371
最短路模板

Luogu P4779
最短路模板

Luogu P1821
正反两次最短路

Luogu P2419
传递闭包

参考资料

Dijkstra's algorithm

SPFA

P2176

https://www.luogu.com.cn/problem/P2176
[USACO11DEC]RoadBlock S / [USACO14FEB]Roadblock G/S

暴力的思路： 枚举哪条边 * 2，重新求最短路
时间复杂度 m * 最短路的时间复杂度

一定是把最短路上的某条边 * 2，只需要枚举至多 n-1 条边
We must double something in the shortest path. (There are at most n-1 edges)

枚举所有可能的边，重新计算最短路
Try all possible edges, calculate the shortest path again. Brute Froce

分层图最短路
shortest path on multi-layer graph

P4568

https://www.luogu.com.cn/problem/P4568
Shortest path on a graph, but we can use kk edges without cost.

d[i][j]. from start to i, used j free rides.
d[i][j] 从起点到i，使用了j次

https://www.luogu.com.cn/problemnew/solution/P4568

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > points;

minimum priority queue

by default it's less<pair<int, int> >.

P2939 [USACO09FEB]Revamping Trails G

multi layer shortest path
分层图最短路

不同层之间是有向无环图
可以一层一层用 Dijkstra 做
不同层之间直接更新

solve it layer by layer

(k+1) dijsktra

P5837 [USACO19DEC]Milk Pumping G

http://usaco.org/index.php?page=viewproblem2&cpid=969

Minimize flow/cost

The number of edges is small.

Enumerate the edge with minimum flow, and then all edges with greater flow can be used.

Calculate the minimum cost. Use flow/cost to update the answer.

One time O(mlog⁡n)O(m \log n)

In total O(m2log⁡n)O(m^2 \log n)

P1821 [USACO07FEB]Silver Cow Party S

The shortest paths from X to the other vertices and from the other vertices to X.

Reverse every edge in the graph, and dijkstra again.

P2865 [USACO06NOV]Roadblocks G

方法1：

The (strict) second shortest path.
严格次短路

Enumerate the edge which is not in the shortest path.
次短路上的某条边一定不在最短路上

枚举这条边

starting vectex -> the start of the edge -> the end of the edge -> ending vectex.
起点 -> 枚举的边的起点 -> 枚举的边的终点 -> 终点

方法2：

https://www.luogu.com.cn/blog/Aiz-Wallenstein/solution-p2865

2 distance array.
2个距离数组

d[i] The length of shortest path
d[i] 最短距离

d2[i] The length of second shortest path
d2[i] 次短距离，必须严格大于d[i]

P3659 [USACO17FEB]Why Did the Cow Cross the Road I G

http://usaco.org/index.php?page=viewproblem2&cpid=717
Assume move 3 steps at once, so there are 16 ways to move.
In this problem, the weight is not 1, so priority_queue/set is needed.

CF938D Buy a Ticket

http://codeforces.com/problemset/problem/938/D
Given an undirected graph.

if (a[u[i]] > a[v[i]] + 2 * w[i])
{
    a[u[i]] = a[v[i]] + 2 * w[i];
}

BFS

BFS可以处理边权为1的最短路，参考单独页面 BFS

DAG中的最短路

P6145

P6145 [USACO20FEB]Timeline G
http://usaco.org/index.php?page=viewproblem2&cpid=1017

if (d[b] < d[a] + x)
{
    d[b] = d[a] + x;
}

(a, b, x) forms no cycles. Update them in topological order.

CF666B World Tour

http://codeforces.com/problemset/problem/666/B

Given a directed graph with n(<=3000) vertices and m(<=5000) edges.

The length of edges are 1.

Find 4 distinct vertices A, B, C, D

Maximize dist(A,B) + dist(B, C) + dist(C, D)

FIrst, precalculate the distance from i to every other vertices.

O(n(n+m))O(n(n + m))

For each vertex, calculate the farthest one, second farthest, third farthest vertex.

From ... to x

From x to ...

Enumerate B, C

A must be in (the farthest one, second farthest, third farthest) of B

D must be in (the farthest one, second farthest, third farthest) of C

CF986A Fair

http://codeforces.com/problemset/problem/986/A

Time complexity O(k * (n + m))
For each color, do BFS with multi starting vertices.

差分约束

简介

差分约束系统（System of Difference Constraints），是求解关于一组变数的特殊不等式组之方法。

如果一个系统由 nn 个变量和 mm 个约束条件组成，其中每个约束条件形如
xj−xi≤bk(i,j∈[1,n],k∈[1,m])x_j - x_i \leq b_k (i,j \in [1, n], k \in [1, m])，则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
如果xi−xj≤dx_i - x_j \leq d。

那么从jj向ii连接一条长度为dd的边。

这样求最短路，一定满足xi≤xj+dx_i \leq x_j + d。

判断有无解

判断图有没有负环即可，如果发现了负环，说明找到了矛盾。

值得注意的是这个负环问题是全局有没有负环，所以看起来需要所有点同时入队。

求出一组解

有的时候不仅要判断一组解，而需要求出一组解。

参考题目

Luogu P1250

Luogu P1993

P1339 [USACO09OCT]Heat Wave G
P5837 [USACO19DEC]Milk Pumping G
P3659 [USACO17FEB]Why Did the Cow Cross the Road I G
P6145 [USACO20FEB]Timeline G
P1339 [USACO09OCT]Heat Wave G
P1821 [USACO07FEB]Silver Cow Party S
P2865 [USACO06NOV]Roadblocks G
CF938D Buy a Ticket
CF666B World Tour
CF986A Fair

O(k(n+m))O(k (n + m))

d[i][j] the shortest time to move good jj to vertex ii.

https://arc061.contest.atcoder.jp/tasks/arc061_c
https://www.luogu.com.cn/problem/AT2069
http://acm.hdu.edu.cn/showproblem.php?pid=6386

Wrong Solution:

https://arc061.contest.atcoder.jp/submissions/1655604

#include<iostream>
#include<set>
#include<queue>
using namespace std;
struct edge{int to,color;};
vector<edge> w[100010];
int n,m,d[100010];
set<int> s[100010];
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        w[a].push_back({b,c});
        w[b].push_back({a,c});
    }
    d[1]=0;
    for(int i=2;i<=n;i++)d[i]=1e6;
    priority_queue<pair<int,int>> q;
    q.push({-d[1],1});
    while(q.size())
    {
        int now=q.top().second,cost=-q.top().first;q.pop();
        if(d[now]<cost) continue;
        for(edge j:w[now])
        {
            int dist=d[now];
            if(!s[now].count(j.color)) dist++;
            if(dist<d[j.to])
            {
                d[j.to]=dist;
                s[j.to].clear();
                s[j.to].insert(j.color);
                q.push({-d[j.to],j.to});
            }
            else if(dist==d[j.to])
            {
                // if (j.color not in s[j.to])
                {
                    s[j.to].insert(j.color);
                    // q.push({-d[j.to],j.to});
                }
            }
        }
    }
    if(d[n]>4e5)cout<<-1<<endl;
    else cout<<d[n]<<endl;
    return 0;
}
/*
4 6
1 2 1
2 3 1
3 4 1
1 3 2
3 2 2
2 4 3
*/
https://arc061.contest.atcoder.jp/submissions/1655604

P2939 [USACO09FEB]Revamping Trails G

不需要 long long
一层一层 做最短路

阅读其他

graph_storage
BFS
dijkstra
floyd
bellman_ford
priority_queue
diff_constraints

  1. 最短路 Shortest Path
    1. 图的存储
    2. 基本性质
    3. Bellman Ford
      1. Bellman Ford
      2. P1938 [USACO09NOV]Job Hunt S
  2. Dijkstra
    1. Dijkstra
    2. 参考题目
      1. spoj ADRABR
      2. P5201 [USACO19JAN]Shortcut G
      3. P5122 [USACO18DEC]Fine Dining G
      4. P1629 邮递员送信
      5. P4779 【模板】单源最短路径（标准版）
      6. bzoj 3040
    3. Floyd
      1. Floyd
      2. P2910 [USACO08OPEN]Clear And Present Danger S
      3. CF25C
    4. Floyd算法的应用
      1. P6175 无向图的最小环问题
      2. P1119 灾后重建
    5. 用 bitset 做传递闭包 use bitset to maintain
      1. P4306 [JSOI2010]连通数
  3. SPFA
    1. 队列优化版的Bellman Ford
      1. SPFA (Only in China, useless)
    2. SPFA
    3. 其他变形
    4. 参考题目
    5. 参考资料
      1. P2176
      2. P4568
      3. P2939 [USACO09FEB]Revamping Trails G
      4. P5837 [USACO19DEC]Milk Pumping G
      5. P1821 [USACO07FEB]Silver Cow Party S
      6. P2865 [USACO06NOV]Roadblocks G
      7. P3659 [USACO17FEB]Why Did the Cow Cross the Road I G
      8. CF938D Buy a Ticket
    6. BFS
    7. DAG中的最短路
      1. P6145
      2. CF666B World Tour
      3. CF986A Fair
  4. 差分约束
    1. 简介
    2. 判断有无解
    3. 求出一组解
    4. 参考题目
      1. P2939 [USACO09FEB]Revamping Trails G
    5. 阅读其他
≡