题目：P6464 [传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：先用Floyd算法求出所有点之间的最短路径距离，得到A矩阵（由于不需要求具体路径，所有不需要Path矩阵）。然后挨个去设置开启传送门的两点。设置之后分别将两点设置为中转点，再去遍历A矩阵，更新每两个点之间的最短路径距离，然后总的和，求出所有和里面最小的那个，就是题目所求。

代码：

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
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> graph(n, vector<int>(n, 1e9));
	for (int i = 0; i < n; i++)
	{
		graph[i][i] = 0;
	}
	for (int i = 0; i < m; i++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		graph[x - 1][y - 1] = w;
		graph[y - 1][x - 1] = w;
	}

#pragma region Floyd算法
	for (int v = 0; v < n; v++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				graph[i][j] = min(graph[i][j], graph[i][v] + graph[v][j]);
			}
		}
	}
#pragma endregion



	long dis = INT_MAX;

	vector<vector<int>> A;

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) //i,j为遍历选择建立传送门的两点
		{

			A = graph; //重置A数组

			A[i][j] = A[j][i] = 0;  //设置i，j两点开启传送门，距离重置为0 

			//以i点为中转点，更改最短路径
			for (int k1 = 0; k1 < n; k1++)
				for (int k2 = 0; k2 < n; k2++)
					A[k1][k2] = min(A[k1][k2], A[k1][i] + A[i][k2]);

			//以j点为中转点，更改最短路径
			for (int k1 = 0; k1 < n; k1++)
				for (int k2 = 0; k2 < n; k2++)
					A[k1][k2] = min(A[k1][k2], A[k1][j] + A[j][k2]);

			long res = 0;
			for (int k1 = 0; k1 < n; k1++)
				for (int k2 = k1 + 1; k2 < n; k2++)
					res += A[k1][k2];//遍历矩阵的上三角或者下三角求和（因为题目说单边只统计一次）
			dis = min(dis, res);
		}
	cout << dis;
	return 0;
}