自动搬运

查看原文

来自洛谷，原作者为

	Fontainebleau ゆき

搬运于2025-08-24 22:21:01，当前版本为作者最后更新于2020-06-28 21:29:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

期末考前一天发题解求 $rp$ 。

这道题一看数据范围 $n≤100$ 。暴力石锤了。

很容易想到 $Floyd$ 。

先算未建传送门时的最短路。接着两所学校两所学校枚举，求建传送门的最优方案。

要开两个数组，

int f[101][101];
int F[101][101];

$f[i][j]$ 表示未建传送门时的 $i$ 到 $j$ 的最短路。

$F[i][j]$ 表示建了传送门之后 $i$ 到 $j$ 的最短路。

改上代码了~

#include<bits/stdc++.h>
#define FOR(i,j,k)  for(int i=(j);i<=(k);i++)
using namespace std;
int n,m;
int f[101][101];
int F[101][101];
inline void back()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			F[i][j]=f[i][j];
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(f,-1,sizeof(f));
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(f[u][v]==-1||f[u][v]>w)	f[u][v]=f[v][u]=w;//建边，防重边（不过数据里没有）
	}
	for(int k=1;k<=n;k++)	
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(f[i][k]!=-1&&f[k][j]!=-1)
					if(f[i][j]==-1||f[i][j]>f[k][j]+f[i][k])
						f[i][j]=f[i][k]+f[k][j];//Floyd
	int ans=2e9;//较大值
	for(int i=1;i<=n;i++)	
		for(int j=1;j<=n;j++)//暴力枚举
		{
			back();//先让F数组还原成f数组
			F[i][j]=F[j][i]=0;//在教学楼 i 和 j 之间建立传送门
			for(int x=1;x<=n;x++)	
				for(int y=1;y<=n;y++)	
					if(F[x][y]==-1||F[x][y]>F[x][i]+F[i][y])
						F[x][y]=F[x][i]+F[i][y];//Floyd
			for(int x=1;x<=n;x++)
				for(int y=1;y<=n;y++)	
					if(F[x][y]==-1||F[x][y]>F[x][j]+F[j][y])
						F[x][y]=F[x][j]+F[j][y];//Floyd
			int res=0;
			for(int x=1;x<=n;x++)	
				for(int y=1;y<x;y++)
					res+=F[x][y];
			ans=min(res,ans);
		}
	printf("%d\n",ans);
	return 0;
}

为什么这里 $↓$ 要这么算呢

			for(int x=1;x<=n;x++)	
				for(int y=1;y<=n;y++)	
					if(F[x][y]==-1||F[x][y]>F[x][i]+F[i][y])
						F[x][y]=F[x][i]+F[i][y];
			for(int x=1;x<=n;x++)
				for(int y=1;y<=n;y++)	
					if(F[x][y]==-1||F[x][y]>F[x][j]+F[j][y])
						F[x][y]=F[x][j]+F[j][y];

因为建立了传送门，只有使用传送门才会影响当前最短路。

$❀$ 完结撒花 $❀$