最短路之和
给定一个 $n$ 个点的加权有向图，点的编号为 $1 \sim n$。
图中任意两点之间都有两条方向相反的边连接两点。
从点 $i$ 到点 $j$ 的边的长度为 $a_{ij}$。
给定一个 $1 \sim n$ 的排列 $x_1,x_2, \ldots ,x_n$。
你需要对该图依次进行 $n$ 个操作。
其中，第 $i$ 个操作是将点 $x_i$ 以及该点的所有入边和出边从图中移除。
在执行每一个操作之前，你还需要进行如下计算：
- 对于每个当前剩余点对 $(u,v)$，计算从点 $u$ 到点 $v$ 的最短路长度。
- 将这些最短路长度全部相加得到最短路之和。
注意：
- 剩余点对 $(u,v)$：两个还未被移除的点 $u,v$（$u \ne v$）组成的点对。
- $(u,v)$ 和 $(v,u)$ 是两个不同点对，需分别计算最短路长度并计入最短路之和。
- $n$ 个操作是按顺序依次执行的，前面的操作会对后面的计算产生影响。
请你输出执行每个操作前计算得到的最短路之和。
输入格式
第一行包含整数 $n$。
接下来 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行第 $j$ 个数为 $a_{ij}$。
最后一行包含 $n$ 个整数 $x_1,x_2, \ldots ,x_n$。
输出格式
共一行，输出 $n$ 个整数，其中第 $i$ 个整数表示执行第 $i$ 个操作之前，计算得到的最短路之和。
数据范围
前 $4$ 个测试点满足 $1 \leq n \leq 4$。
所有测试点满足 $1 \leq n \leq 500$，$1 \leq a_{ij} \leq {10}^{5}$，$a_{ii}=0$，$1 \leq x_i \leq n$，保证 $x_1 \sim x_n$ 是一个 $1 \sim n$ 的排列。
输入样例1：
1 0 1
输出样例1：
0
输入样例2：
2 0 5 4 0 1 2
输出样例2：
9 0
输入样例3：
4 0 3 1 1 6 0 400 1 2 4 0 1 1 1 1 0 4 1 2 3
输出样例3：
17 23 404 0
解题思路
比赛的时候猜对了做法，这题本质就是考对Floyd算法原理的理解。
因为这题要求任意两点间的最短路径，所以首先容易想到用Floyd。然后就是每次从点集中删除一个点，求点集中剩余点的任意两点间的最短距离的总和。删点的话不好做，那么试试倒过来做行不行。就是一开始点集为空，然后每次往点集中加入一个点（以及对应的边），再求点集中任意两点最短路。如果了解Floyd算法的原理的话那么就会知道，当第一层循环枚举完$k$，此时求得的是任意两点间只经过节点编号$1 \sim k$的最短距离。因此每次我们当我们枚举到$k$，那么就可以求出任意两点间只经过前$k$个点的最短距离，而前$k$个点就是我们往点集中加的前$k$个点。
下面补个Floyd的推导过程，其实本质就是个dp。
定义状态$f(k,i,j)$表示所有从$i$出发，最终走到$j$，且中间只经过节点编号不超过$k$的所有路径，属性就是路径长度的最小值。根据$i \to j$的路径中（不包含起点$i$和终点$j$）是否包含节点$k$来划分集合。
- 如果$i \to j$的路径不包含节点$k$，那么意味着当前$i \to j$的所有路径中只含有节点$1 \sim k-1$，对应的集合就是$f(k-1,i,j)$。
- 如果如果$i \to j$的路径包含节点$k$，那么有$i \to \cdots \to k \to \cdots \to j$，其中$i \to \cdots \to k$和$k \to \cdots \to j$的路径中只含有节点$1 \sim k-1$，分别对应的集合为$f(k-1,i,k)$和$f(k-1,k,j)$。
对这两种情况取最小值，那么就有状态转移方程$$f(k,i,j) = \min \left\{ {f(k-1,i,j),\ f(k-1,i,k)+f(k-1,k,j)} \right\}$$
然后就是证明把状态定义的第一维$k$去掉得到的$f(i,j)$与原本的状态是等价的。
当$j = k$时，原本有$f(k,i,k) = \min \left\{ {f(k-1,i,k),\ f(k-1,i,k)+f(k-1,k,k)} \right\}$，由于$f(k-1,k,k) = 0$（初始化的时候有$f(0,k,k) = 0$，即$k$到本身的最小距离为$0$），因此得到$f(k,i,k) = \min \left\{ {f(k-1,i,k),\ f(k-1,i,k)} \right\} = f(k-1,i,k)$。因此对于$j=k$的情况去掉第一维不会影响结果，因为状态$f(i,k)$存的是上一层的$f(i,k)$的结果。
同理当$i = k$时，原本有$f(k,k,j) = \min \left\{ {f(k-1,k,j),\ f(k-1,k,k)+f(k-1,k,j)} \right\}$，由于$f(k-1,k,k) = 0$，因此得到$f(k,k,j) = \min \left\{ {f(k-1,k,j),\ f(k-1,k,j)} \right\} = f(k-1,k,j)$。因此对于$i=k$的情况去掉第一维不会影响结果，因为状态$f(k,j)$存的是上一层的$f(k,j)$的结果。
对于一般的$f(k,i,j)$，有$$\begin{align*} f(k,i,j) &= \min \left\{ {f(k-1,i,j),\ f(k-1,i,k)+f(k-1,k,j)} \right\} \\ &= \min \left\{ {f(k-1,i,j),\ f(k,i,k)+f(k,k,j)} \right\} \end{align*}$$
因此去掉第一维可以发现$f(i,j) = \min \left\{ {f(i,j),\ f(i,k)+f(k,j)} \right\}$，与之前的状态转移方程是等价的。
因此状态转移方程就可以写成$$f(i,j) = \min \left\{ {f(i,j),\ f(i,k)+f(k,j)} \right\}$$
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5
6 const int N = 510;
7
8 LL g[N][N];
9 int p[N];
10 LL ans[N];
11
12 int main() {
13 int n;
14 scanf("%d", &n);
15 for (int i = 1; i <= n; i++) {
16 for (int j = 1; j <= n; j++) {
17 scanf("%lld", &g[i][j]);
18 }
19 }
20 for (int i = 1; i <= n; i++) {
21 scanf("%d", p + i);
22 }
23 for (int k = n; k; k--) { // 倒序插入点，求只经过p[k]~p[n]的最短路径
24 for (int i = 1; i <= n; i++) {
25 for (int j = 1; j <= n; j++) {
26 g[i][j] = min(g[i][j], g[i][p[k]] + g[p[k]][j]);
27 }
28 }
29 for (int i = n; i >= k; i--) { // 只统计已加入的点的结果
30 for (int j = n; j >= k; j--) {
31 ans[k] += g[p[i]][p[j]];
32 }
33 }
34 }
35 for (int i = 1; i <= n; i++) {
36 printf("%lld ", ans[i]);
37 }
38
39 return 0;
40 }
参考资料
AcWing 4872. 最短路之和（AcWing杯 - 周赛）：https://www.acwing.com/video/4653/
3.2 floyd算法及其扩展应用：https://www.acwing.com/file_system/file/content/whole/index/content/147349/
标签：right,min,int,短路,leq,left From： https://www.cnblogs.com/onlyblues/p/17208630.html