怎么做网站详情页,百度手机助手,备案域名出租,常熟做公司网站文章目录 [USACO09JAN] 最佳牧场 S题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 思路解析CODE [USACO09JAN] 最佳牧场 S
题目链接#xff1a;https://www.luogu.com.cn/problem/P2935
题目描述
贝茜#xff0c;总是希望优化她的生活#xff0c;她发现自己… 文章目录 [USACO09JAN] 最佳牧场 S题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 思路解析CODE [USACO09JAN] 最佳牧场 S
题目链接https://www.luogu.com.cn/problem/P2935
题目描述
贝茜总是希望优化她的生活她发现自己真的很喜欢访问农夫约翰的P (1 P 500)个牧场中的F (1 F P)个她最喜欢的牧场F_i。
贝茜知道她可以通过C (1 C 8,000)条双向的牛道方便地编号为1…C来连接各个牧场以便在整个农场的任何牧场之间旅行。每条路径P_i都有一个时间T_i (1 T_i 892)来穿越该路径无论哪个方向和两个路径端点a_i和b_i (1 a_i P; 1 b_i P)。
贝茜想找到最好的牧场来睡觉这样当她醒来时到达她的F个最喜欢的牧场的平均时间就最小了。
举例来说考虑一个农场的布局如下图所示其中*d牧场编号是最喜欢的。括号中的数字是穿越牛道的时间。
1*--[4]--2--[2]--3| |[3] [4]| |4--[3]--5--[1]---6---[6]---7--[7]--8*| | | |[3] [2] [1] [3]| | | |13* 9--[3]--10*--[1]--11*--[3]--12*以下表格显示了牧场4、5、6、7、9、10、11和12的潜在’最佳位置’的距离 * * * * * * 最喜欢的 * * * * * *潜在的最佳 牧场 牧场 牧场 牧场 牧场 牧场 平均
牧场 1 8 10 11 12 13 距离
------------ -- -- -- -- -- -- -----------4 7 16 5 6 9 3 46/6 7.675 10 13 2 3 6 6 40/6 6.676 11 12 1 2 5 7 38/6 6.337 16 7 4 3 6 12 48/6 8.009 12 14 3 4 7 8 48/6 8.0010 12 11 0 1 4 8 36/6 6.00 ** 最佳11 13 10 1 0 3 9 36/6 6.0012 16 13 4 3 0 12 48/6 8.00
因此假设这些选择是最好的一个程序必须以某种方式检查所有的选择最好的睡觉地点是牧场10。
约翰拥有P(1P500)个牧场.贝茜特别喜欢其中的F个.所有的牧场 由C(1 C8000)条双向路连接第i路连接着ai,bi需要Ti(1Ti 892)单 位时间来通过.
作为一只总想优化自己生活方式的奶牛贝茜喜欢自己某一天醒来到达所有那F个她喜欢的 牧场的平均需时最小.那她前一天应该睡在哪个牧场呢请帮助贝茜找到这个最佳牧场.
此可见牧场10到所有贝茜喜欢的牧场的平均距离最小为最佳牧场.
输入格式
* 第1行三个空格分隔的整数P、F和C
* 第2行到F1行第i2行包含一个整数F_i
* 第F2行到CF1行第iF1行用三个空格分隔的整数描述牛道ia_i、b_i和T_i
输出格式
* 第1行一行一个整数表示最好的牧场在哪里睡觉。如果有多个牧场是最好的选择最小的那个。
样例 #1
样例输入 #1
13 6 15
11
13
10
12
8
1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7样例输出 #1
10提示
如题目所述
如题目所述。 思路解析
用 F l o y d Floyd Floyd 算法将多源最短路算出多源点的最短路距离最后加起来比较即可。 CODE
#include iostream
#include vector
#include cstring
#include algorithm
#include queue
#define ll long long
#define INF 0x3f3f3f3f using namespace std;typedef pairint, int pii;const int N 520, M 8010;
int d[N][N]; // 存储每个节点之间的最短距离
int n, m, k; // n是节点数k是喜欢的节点数m是边的数目
vectorint love; // 存储喜欢的节点// Floyd-Warshall算法用于计算所有节点对之间的最短路径
void floyd(){for(int k 1; k n; k)for(int i 1; i n; i)for(int j 1; j n; j)d[i][j] min(d[i][j], (d[i][k] INF || d[k][j] INF) ? INF : d[i][k] d[k][j]);
}int main(){cin n k m; // 输入节点数喜欢的节点数边的数目// 初始化距离矩阵for(int i 1; i n; i)for(int j 1; j n; j)d[i][j] (i j ? 0 : INF);// 输入喜欢的节点while(k--){int f;scanf(%d, f);love.push_back(f); }// 输入边的信息while(m--){int a, b, w;scanf(%d%d%d, a, b, w);d[a][b] d[b][a] min(d[a][b], w);}// 计算所有节点对之间的最短路径floyd();int ans 0, res INF; // 初始化答案和最小平均距离// 遍历所有节点找到平均距离最小的节点for(int i 1; i n; i){int tmp 0;for(int j 0; j love.size(); j){tmp d[i][love[j]];}if(res tmp){res tmp;ans i;}}cout ans; // 输出结果
}
唯一需要注意的点就是res要初始化成一个很大的数不然会影响后续记录最小的点
