本文主要是介绍洛谷 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);
}
这篇关于洛谷 P2935 [USACO09JAN]最好的地方Best Spot的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!