题解 P6464 【传送门】

这数据范围显然是 Floyd 裸题啊啊啊。 ## 题目大意 传智专修学院里有 $n$ 栋教学楼，有 $m$ 条**双向通行道路**连接这些教学楼，**不存在重边和自环**。每条道路都有一定的长度，而且所有教学楼之间都可以直接或者间接的通过道路到达。我们可以很容易的求出这些教学楼之间的最短路。 为了使交通更为顺畅，校方决定在两个教学楼里增设一对传送门。传送门可以将这对教学楼的距离直接缩短为 $0$。利用传送门，某些教学楼之间的最短路的距离就变短了。 由于预算有限，学校里只能安装**一对**传送门。但是校长希望尽可能方便学生，**使任意两点之间的最短路长度的总和最小**。当然啦，从 $x$ 教学楼到 $y$ 教学楼的长度和从 $y$ 教学楼到 $x$ 教学楼的长度只需要统计一次就可以了。 ## 大体思路 给定一个各个点相互联通的无向图，我们可以选择在这个无向图中的两点假设一个传送门，使这两个点的距离变为 $0$，当这两个点的距离为 $0$ 之后，这样就有可能影响其他点对点之间的最短距离，问我在任意点对之间架设一个传送门之后，任意点对之间的最短路距离之和最小为多少。 这一题，题目已经给了提示，任意点对，能求任意点对点之间的最短距离只有 floyd 算法了（[全源最短路](https://www.luogu.com.cn/problem/P5905)），用 floyd 跑完多元最短路之后 $O(n^3)$，剩下就是暴力枚举。 任意一个点对设为 $(i,j)$ 在这个点对上架设传送门,这里复杂度为 $O(n^2)$，在假设个传送门之后，我们考虑，除了 $(i,j)$ 点对之外，枚举其他点对设为 $(a,b)$ ，这里复杂度为 $O(n^2)$，会收到这个传送门的什么影响呢？设一个点 $x,y$ 在跑完 floyd 之后对最短路距离为 `dp[x][y] == dp[y][x]`，考虑如果 $a$ 到 $b$ 点最短路不经过 $(i,j)$ 这一边的话，那么 $a$ 到 $b$ 之间的最短路距离是不会被影响的，反之如果经过了 $(i,j)$ 这条路的化（经过的情况可以是 $a\to i\to j\to b$、$a\to j\to i\to b$），那么 $a$ 到 $b$ 之间的距离肯定会被影响，这个时候 $a$ 到 $b$ 之间的最短路距离是 $\min\left\{dp(a,b),\min( dp(a,i) + dp(j,b), dp(a,j) + dp(i,b))\right\}$。 ## 完整代码 ```cpp #include<bits/stdc++.h> const int INF = 0x3f3f3f3f; using namespace std; const int maxn = 1e105; int dp[maxn][maxn];//抄袭有奖qaq int main(){ int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) if(i == j) dp[i][j] = 0; else dp[i][j] = INF; int u, v, w; for(int i = 0; i < m; i ++) { scanf("%d %d %d", &u, &v, &w); //建立双向边 dp[u][v] = w; dp[v][u] = w; } //floyd 算法 for(int k = 1; k <= n; k ++) for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); //假设假设建立传送门的点对为（i，j）(默认j > i)，枚举减少的距离任意一个点对点（a, b）（这里默认b > a）距离为 int ans = INF, res; for(int i = 1; i < n; i ++) for(int j = i + 1; j <= n; j ++) { res = 0; for(int a = 1; a < n; a ++) for(int b = a + 1; b <= n; b ++) if(a != i || b != j) res += min(dp[a][b], min(dp[a][i] + dp[j][b], dp[a][j] + dp[i][b])); ans = min(ans, res); } printf("%d\n", ans); return 0; } ``` 题目来源：第二届“传智杯”全国大学生 IT 技能大赛（决赛）。