P2935 [USACO09JAN]最好的地方Best Spot
Cxs3
·
·
题解
题目链接：https://www.luogu.org/problemnew/show/P2935
这题的题解好少呢，我也发布一篇吧
题目分析
题目要求哪个点与F个点的距离（即题面中的时间）和最小，就得求出每个点分别到这F的点的最小距离，可用 且 只能用Floyd.
步骤：
$2.$枚举每个点，算出距离总和，同时找距离和最小的一个点记录下标；
$3.$输出这个下标即可。
时间复杂度$O(n^3)$.
~~也快不到哪里去了QAQ~~
---
## 代码实现
这次就放完整代码了qwq：
```cpp
#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