洛谷 P2935 [USACO09JAN]最好的地方Best Spot

题目传送门
.
.
.
.
.

分析

水题一道
先用Flody算出各点之间的最短路
求和点到F_i的距离
再比较谁更短即可
.
.
.
.
.

程序：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int p,f,c,fi[1000],g[510][510]; int main() {scanf("%d%d%d",&p,&f,&c);for (int i=1;i<=f;i++) scanf("%d",&fi[i]);memset(g,0x3f,sizeof(g));for (int i=1;i<=c;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);g[u][v]=g[v][u]=w;}for (int i=1;i<=p;i++)g[i][i]=0;for (int k=1;k<=p;k++)for (int i=1;i<=p;i++)for (int j=1;j<=p;j++)if (g[i][k]+g[k][j]<g[i][j]) g[i][j]=g[i][k]+g[k][j];int ans=0,bz=2147483647;for (int i=1;i<=p;i++){int sum=0;for (int j=1;j<=f;j++)sum+=g[i][fi[j]];if (sum<bz) {bz=sum;ans=i;}}printf("%d",ans); }

转载于:https://www.cnblogs.com/YYC-0304/p/10292853.html

总结

以上是生活随笔为你收集整理的洛谷 P2935 [USACO09JAN]最好的地方Best Spot的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。