2017 年腾讯 秋招软件开发笔试编程题回忆版
（所有题目大致描述如下，并非完整的题目回忆，但意思大致一样）
1、又一个魔法城市，城市里面有n个魔法城堡，序号为0，1，2。。。n-1；魔法城堡之间都有路径相连；魔法城堡两两之间的到达的距离不同，因此所需时间也可能不会相同。如魔法城堡0到魔法城堡2需要耗时4小时；现，小明想从魔法城堡0到魔法城堡1，他想知道需要花费多少时间；为了快速到达，有一魔法扫把，魔法扫把使用次数有限，使用一次，可以将某一段间的时间减半；求小明从魔法城堡0到魔法城堡1花费的最小时间，精确到一位小数。
输入：总共n+1行；
第一行，魔法城堡数n；魔法扫把能够使用的次数k；
第二行到第n行为魔法城堡之间到达需要的时间；
输出：从魔法城堡0到魔法城堡花费的最短时间：t，精确到小数点后一位。
示例：
输入：
3 2
094
904
440
（注：腾讯这里输入的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 MIN 99999
vector
{
int size = arcs.size();
vector
vector
vector
//初始化
for (size_t i = 0; i < size; i++)
{
dist[i] = arcs[0][i];
S[i] = 0;
path[i] = 0;
}
S[0] = 1, path[0] = -1;
//进行循环更新每次遍历每个节点的最短路径长度
for (int i = 1; i < size; i++)
{
int nmin = MIN, mi = 1;
for (int j = 1; j < size; j++)
{
if (!S[j] && dist[j] < nmin)
{
mi = j;
nmin = dist[j];
}
}
cout << “min index=” << mi << “; paht=”<
Original: https://www.cnblogs.com/kingpop/p/7520235.html
Author: KingPop
Title: 2017年腾讯 秋招软件开发笔试编程题回忆版
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/577882/
转载文章受原作者版权保护。转载请注明原作者出处！