首页 > 试题广场 >

星球游戏

[编程题]星球游戏
  • 热度指数：228 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

牛牛和牛妹在进行一场星球模拟游戏，游戏规则如下：

游戏地图内共有n个星球，共有m条隧道连接这些星球。每条隧道都是双向的，每两个星球间不一定只有一条隧道。现在牛牛占领了这n个星球中的p个星球，牛妹占领了这n个星球中的q的星球（每个星球最多只能被一个人占领）。现在牛牛想知道他占领的p个星球中任意一个星球，到牛妹占领的q个星球中任意一个星球，这两个星球的最短距离是多少。

示例1

输入

[1],[3,4],[[1,2,7],[2,3,6],[3,4,2],[1,3,11],[2,4,3]],4

输出

10

说明

距离最近的牛牛星和牛妹星是1和4，他们之间的距离为10
示例2

输入

[1],[2],[],2

输出

-1

说明

所有的牛牛星和牛妹星都不联通，故输出-1

备注:
对于50%的数据：

对于100%的数据：
  相关参数意义如下
  serialP 牛牛占领的p个星球的编号
  serialQ 牛妹占领的q个星球的编号
  path  m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
  nn int整型 星球个数n

算法知识视频讲解
开通博客
头像 GhostLX
发表于 2021-07-25 15:27:15
题目描述 牛牛和牛妹在进行一场星球模拟游戏，游戏规则如下： 游戏地图内共有n个星球，共有m条隧道连接这些星球。每条隧道都是双向的，每两个星球间不一定只有一条隧道。现在牛牛占领了这n个星球中的p个星球，牛妹占领了这n个星球中的q的星球（每个星球最多只能被一个人占领）。现在牛牛想知道他占领的p个星球中任 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 CCSU—JPanel
发表于 2021-06-17 13:31:06
描述 牛牛和牛妹在进行一场星球模拟游戏，游戏规则如下： 游戏地图内共有n个星球，共有m条隧道连接这些星球。每条隧道都是双向的，每两个星球间不一定只有一条隧道。现在牛牛占领了这n个星球中的p个星球，牛妹占领了这n个星球中的q的星球（每个星球最多只能被一个人占领）。现在牛牛想知道他占领的p个星球中任意一 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Bug-Maker
发表于 2021-07-12 20:21:59
从牛牛所占有的所有星球出发，向外扩张，当第一次触碰到牛妹的星球时，跳出循环。 class Solution { public:     /**      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-09-10 17:15:08
题意整理 有n个星球，星球之间通过m条隧道连接，牛牛占有p个星球，牛妹占有q个星球。 求从牛牛占有的星球到牛妹占有的星球需要走过的最短距离。 方法一（弗洛伊德算法） 1.解题思路 首先初始化一个二维数组dist，记录每个星球间的距离。 通过给定的隧道，给dist数组赋值。 走弗洛伊德算法，基本 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客313925129号
发表于 2021-09-24 11:22:32
题意理解 n个星球可以看作n个结点，之间有零到多条无向边，牛牛和牛妹占领的星球可以看作两个点集。题目要求，从点集A中的某点到点集B中某点的所需要的最短距离。 方法一 最短路径算法有多种。本题中没有给定起点和终点，而是一个起点的集合A和终点的集合B，所以使用Floryd算法，求得所有结点之间的最短路径 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 不会做题的小菜鸡
发表于 2021-10-20 00:08:00
思路 题目分析 该题是一个寻找图最短路径的问题 题目给出两组节点，根据图内的节点关系求一组到另一组的最短路径，返回这个最短路径 方法一：Floyd算法（超时） 多源最短路径算法 不适用负权回路图 思路 Floyd的方法是通过三轮循环进行，可以求出任意两个节点之间的最短路径 图要先转成 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

图
难度：
1条回答 1669浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号