自动搬运

查看原文

来自洛谷，原作者为

	Cxs3 这个家伙很懒，什么也不想留下

搬运于2025-08-24 21:43:35，当前版本为作者最后更新于2018-08-11 21:38:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目链接：https://www.luogu.org/problemnew/show/P2935
这题的题解好少呢，我也发布一篇吧

题目分析

题目要求哪个点与$F$个点的距离（即题面中的时间）和最小，就得求出每个点分别到这$F$的点的最小距离，可用 且 只能用$Floyd$.

步骤：
$1.$跑一遍$Floyd$；
$2.$枚举每个点，算出距离总和，同时找距离和最小的一个点记录下标；
$3.$输出这个下标即可。

时间复杂度$O(n^3)$.
也快不到哪里去了QAQ

代码实现

这次就放完整代码了qwq：

#include<bits/stdc++.h>
const int inf=0x3fffffff;
using namespace std;
int n,m,p,like[501];//n个点，m条边，p个喜欢的点（因为本人习惯，与题目中有所不同）
int ans,mi=inf,f[501][501];
int main()
{
	int i,j,k,u,v,c,sum;
	cin>>n>>p>>m;
	for(i=1;i<=n;i++)//初始化
	{
	  for(j=1;j<=n;j++) f[i][j]=inf;
	  f[i][i]=0;//点i到点i的最小距离为0
	}
	for(i=1;i<=p;i++) cin>>like[i];
	for(i=1;i<=m;i++)
	{
	  cin>>u>>v>>c;
	  f[u][v]=c;//采用类似邻接矩阵的方式读入
	  f[v][u]=c;
	}
	for(k=1;k<=n;k++)
	  for(i=1;i<=n;i++)
	    for(j=1;j<=n;j++)
	      f[i][j]=min(f[i][j],f[i][k]+f[k][j]);//DP动态转移方程
	for(i=1;i<=n;i++)
	{
	  sum=0;
	  for(j=1;j<=p;j++) sum+=f[i][like[j]];//累加距离和
	  if(sum<mi){mi=sum; ans=i;}//更新答案
	}
	cout<<ans<<endl;
	return 0;
}

愿我的题解能帮到大家，毕竟我只是个蒟蒻qwq