电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

2017年腾讯秋招软件开发笔试编程题

2017年腾讯秋招软件开发笔试编程题_第1页
1/13
2017年腾讯秋招软件开发笔试编程题_第2页
2/13
2017年腾讯秋招软件开发笔试编程题_第3页
3/13
2017 年腾讯秋招软件开发笔试编程题回忆版(所有题目大致描述如下,并非完整的题目回忆,但意思大致一样)1、又一个魔法城市,城市里面有 n 个魔法城堡,序号为 0,1,2。。。n-1;魔法城堡之间都有路径相连;魔法城堡两两之间的到达的距离不同,因此所需时间也可能不会相同。如魔法城堡 0 到魔法城堡 2 需要耗时 4 小时;现,小明想从魔法城堡 0 到魔法城堡 1,他想知道需要花费多少时间;为了快速到达,有一魔法扫把,魔法扫把使用次数有限,使用一次,可以将某一段间的时间减半;求小明从魔法城堡 0 到魔法城堡 1 花费的最小时间,精确到一位小数。输入:总共 n+1 行;第一行,魔法城堡数 n;魔法扫把能够使用的次数 k;第二行到第 n 行为魔法城堡之间到达需要的时间;输出:从魔法城堡 0 到魔法城堡花费的最短时间:t,精确到小数点后一位。示例:输入:3 2094904440(注:腾讯这里输入的 094,904,440,是以字符串的形式输入的)输出:4.0个人大致思路:利用 Dijkstra 最短路径求法;记录到魔法城堡 1 的最短路径上每一个前驱节点和对应的距离;然后对每段的距离进行降序排序;之后把魔法扫把使用在所耗时最多的段中。如 0 到 1 的最短路径为 0 到 2,消耗为 4;2 到 1 消耗为 3;魔法扫把能使用 1 次;那么把这一次机会使用在 0 到 2 这一段路径上;那么最后最短时间即为:2+3=5.0;代码实现为:#include #include #include #include #include #include #include #include using namespace std;#define MINvectordijkstra_shortpath(vector> arcs, intednode){int size = arcs.size();99999vectordist(size); //保存当前最短路径vector path(size);vector S(size);//保存前驱节点//保存已经找到最短路径的节点//初始化for (size_ti = 0; i< size; i++){}S[0] = 1, path[0] = -1;dist[i] = arcs[0][i];S[i] = 0;path[i] = 0;//进行循环更新每次遍历每个节点的最短路径长度for (inti = 1; i< size; i++){intnmin = MIN, mi = 1;for (int j = 1; j < size; j++){if (!S[j] &&dist[j] 查看更多

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

2017年腾讯秋招软件开发笔试编程题

确认删除?
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群