首页 > B-旅行
开通博客写题解
头像 JQK2020
发表于 2020-06-30 21:59:22
题目描述 小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。然而司机也很聪明，他每次从 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 苟且的狮子
发表于 2020-07-27 14:21:12
最小路、枚举 题意： ##分析：版子题，枚举中间点，选两个最大的。注意图并不是连通图，选择的时候不能选自己。 代码： #include<iostream> #include<algorithm> #include<vector> #include<queue 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 夜语声烦-
发表于 2022-06-12 12:47:57
旅行 思路: 每次选一个点作为中间点，然后跑一边单源最短路，记录距离最远的两个点的距离和，答案就是最大的和，注意多组测试数据的初始化，直接套模板 #include <iostream> #include <cstring> #include <queue> #in 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 绝迹的星
发表于 2024-05-19 13:44:12
B-旅行 题意: 给定图, 求 max{ 任取三个点(起点 → 中转 → 终点)的最短路径长度 } 起点 → 中转 → 终点 ⇔ (中转 → 点1) + (中转 → 点2) 枚举中转点c, dijkstra求出c到其他点的最短距离, 在这些最短距离中选择两个最大的即可 import java.i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Severus.
发表于 2020-07-07 22:10:10
题目描述 小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。然而司机也很聪明，他每次 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 sunrise__sunrise
发表于 2020-07-12 18:42:52
题目意思 给出t组数据，每组数据第一行n个节点m条边的无向图给出边权信息，问选其中三个点最短路径之和最大值为多少。 解题思路 既然要我们最短路可能要用到dijkstra，又因为点可以随意确定，所以只要枚举中间点k，对k求最短路里面最长的两条路之和在return主函数判断最大值即可。如果只有一条路记得 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 肖先生~
发表于 2020-07-16 22:37:10
spfa+链式前向星存图 题目大意 首先要明确，不管题目给了多少个城市，题目只需要求三个点之间的最大距离的最短路径，所以我们依次枚举每个中点，让每个点都做一次中点，并跑一次spfa，求出最短路径，然后再求最短路径的最大值就行 细节处理 就是在跑完spfa之后，此时的最短路已经形成，我们所要做的就是求 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”