P6464 【传送门】：原题链接

题意：

       传智专修学院里有 n 栋教学楼，有 m 条双向通行道路连接这些教学楼且带有路径长度w，路径不存在重边和自环，且路径保证每个点都可以到达。现在学校想安装一对传送门，安装传送门的两点距离为0。求怎么样可以使任意两点之间的最短路长度总和最小。

简单思路:

       通过n的数据大小不超过100，且需要求出任意两点之间的最短路长度总和最小，可得Floyd算法（全源最短路）＋暴力枚举最适合本题。

       首先根据题意，我们先对题目通过Floyd算法计算出各个路径在未考虑传送门情况下的短路。 代码如下：

//在使用Floyd算法前必须对mp二维数组进行初始化
void init(){
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if (i!=j)mp[i][j]=inf;
		}
	}
}
//基础floyd模板算法模板 
void floyd(){
	for (int k=1;k<=n;k++)
	{
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=n;j++)
			{
				//注意变量k为跳板，需要放置在最上面。
				//mp[N][N]记录各个路径之间的最短路
				mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
			}
		}
	}
	return ;
}

       在用Floyd算法初步得出未设置传送门的路径后，就可以开始进行愉快的暴力求解了。 代码如下：

	for (int k=1;k<n;k++)
	{
		for (int l=k+1;l<=n;l++)
		{
			//设置res计算在设置传送门后的最短路径。
			int res=0; 
			//遍历各点进行计算。 
			for (int i=1;i<n;i++)
			{
				for (int j=i+1;j<=n;j++)
				{
					//因为设置传送门的两点间距离为0
					//所以当k==i或l==j时直接跳过 
					if (k!=i || l!=j)
					{
						//选择最短路径进行相加。
						//mp[i][j]为未设置传送门前的最短路径
						//mp[i][k]+mp[l][j]为从i点出发通过k到l到达j的路径。
						//即：i->k->l->j
						//mp[i][l]+mp[k][j]同理 
						//该解算是Floyd的另类应用,将传送门替换为原先的k。 
						res+=min(mp[i][j],min(mp[i][k]+mp[l][j],mp[i][l]+mp[k][j]));
					}
				}
			}
            //统计设置传送门后的最短的路径 
			ans=min(ans,res);
		}
	}

       以下是AC代码：

#include <bits/stdc++.h>
using namespace std;

const int N=1e3,inf=0x3f3f3f3f;
int n,m;
int mp[N][N];
int ans=inf;
//基础floyd模板算法模板 
void floyd(){
	for (int k=1;k<=n;k++)
	{
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=n;j++)
			{
				//注意变量k为跳板，需要放置在最上面。
				//mp[N][N]记录各个路径之间的全职 
				mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
			}
		}
	}
	return ;
}

void init(){
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if (i!=j)mp[i][j]=inf;
		}
	}
}

int main(){
	cin >>n>>m;
	init();
	for (int i=1;i<=m;i++)
	{
		int from,to,w;
		cin >>from>>to>>w;
        //注意，本题说明为无向有权图，题目重述可能讲述不清，再此发表宇宙安全申明，讲过了啊~（|_|）~
		mp[from][to]=mp[to][from]=w;
	}
	floyd();
	//首先设置数字对(k,l)为传送门的两点，进行遍历。 
	for (int k=1;k<n;k++)
	{
		for (int l=k+1;l<=n;l++)
		{
			//设置res计算在设置传送门后的最短路径。
			int res=0; 
			//遍历各点进行计算。 
			for (int i=1;i<n;i++)
			{
				for (int j=i+1;j<=n;j++)
				{
					//因为设置传送门的两点间距离为0
					//所以当k==i或l==j时直接跳过 
					if (k!=i || l!=j)
					{
						//选择最短路径进行相加。
						//mp[i][j]为未设置传送门前的最短路径
						//mp[i][k]+mp[l][j]为从i点出发通过k到l到达j的路径。
						//即：i->k->l->j
						//mp[i][l]+mp[k][j]同理 
						//该解算是Floyd的另类应用,将传送门替换为原先的k。 
						res+=min(mp[i][j],min(mp[i][k]+mp[l][j],mp[i][l]+mp[k][j]));
					}
				}
			}
			//统计设置传送门后的最短的路径 
			ans=min(ans,res);
		}
	}
	cout <<ans<<"\n";
}