题解 P6464 【传送门】
_Fontainebleau_
·
·
题解
期末考前一天发题解求 rp 。
这道题一看数据范围 n≤100 。暴力石锤了。
很容易想到 Floyd 。
先算未建传送门时的最短路。接着两所学校两所学校枚举，求建传送门的最优方案。
要开两个数组，
int f[101][101];
int F[101][101];
$F[i][j]$ 表示建了传送门之后 $i$ 到 $j$ 的最短路。
改上代码了~
```cpp
#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;
}
```
为什么这里 $↓$ 要这么算呢
```cpp
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];
```
因为建立了传送门，只有使用传送门才会影响当前最短路。
------------
$❀$ **完结撒花** $❀