P6464 [传智杯 #2 决赛] 传送门

原题链接： P6464 [传智杯 #2 决赛] 传送门

题意：

有 n 栋教学楼， m 条双向通行道路连接这些教学楼路径长度为w，路径不存在重边和自环，保证每个点都可以到达。现在学校想安装一对传送门，安装传送门的两点距离为0。求在最优方案下的任意点对的最短道路之和。

//获取点 目标点 路径权重。
for(int i = 0; i < m; i ++){
    	cin >> u >> to >> w;
        dp[u][to] = w;
        dp[to][u] = w; //因为是无向边所以需要两边获取。
}
//floyed算法
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]);

在用Floyd算法初步得出未设置传送门的路径后，便可以开始求解。

for(int i = 1; i < n; i ++)
{
    for(int j = i + 1; j <= n; j ++){
    	res = 0;//res为设置传送门后的最短路径。
        //遍历各点。
    	for(int a = 1; a < n; a ++){
        	for(int b = a + 1; b <= n; b ++){
            	if(a != i or b != j){//因为设置传送门的两点间距离为0，所以当k==i或l==j时直接跳过
            		res += min(dp[a][b], min(dp[a][i] + dp[j][b], dp[a][j] + dp[i][b]));
                    //选择最短路径进行相加。
				}
			}      
		}
		ans = min(ans, res);//更新设置传送门后的最短的路径
   		}
}

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N = 1e5+10, inf = 0x3f3f3f3f;
const int maxn = 105;
ll dp[maxn][maxn];
ll n, m; 

int main()
{
	ios;
    cin >> 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;
		}
	}
        
    ll u, to, w;
    for(int i = 0; i < m; i ++)
    {
    	cin >> u >> to >> w;
        dp[u][to] = w;
        dp[to][u] = w;
    }
    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]);
    ll 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 or b != j){
            			res += min(dp[a][b], min(dp[a][i] + dp[j][b], dp[a][j] + dp[i][b]));
					}
				}      
			}
			ans = min(ans, res);
        }
        
	}
        
    cout << ans << "\n";
    return 0;
}