最短执行路径

最短执行路径

【华为校园招聘软件】2022-04-20

【编程题目 | 300分】最短执行路径 [ 2022 校园招聘 考试题 ]

编程题 第3/3题

3. 最短执行路径

本题可使用本地IDE编码，不能使用本地已有代码。

无跳出限制，编码后请点击 “保存并提交” 按钮进行代码提交。

解答要求

时间限制:C/C++ 1000ms | 其他语言 2000ms

空间限制:C/C++ 256MB | 其他语言 512MB

64bit IO Format:%lld

■ 题目描述

给定一颗二叉树，节点id（权值）代表可执行的任务数，同时代表执行该节点的一个固定的运行时间。

父子节点之间可以跳转，跳转消耗的时间为两个节点权值之差的绝对值。

现在需要执行task个任务，需要在二叉树中找一条路径（可由任意节点开始，路径中一个节点出现一次）完成任务（即路径上所有节点的可执行任务数之和>=task），

要求耗时最短，并返回所耗时间（消耗时间为节点运行时间之和 + 路径跳转所消耗时间之和）。

如果没有能完成任务的路径，返回-1。

输入

第一行：n 节点个数

第二行：id[n] 节点id数组

第三行：pid[n] 节点对应的父节点数组，为0代表此节点为根节点

第四行：task 任务数

输出

最短执行路径耗时大小

样例

输入

8

16 12 3 10 5 2 4 1

0 16 16 12 3 3 2 2

7

输出

10

代码实现

C++

#include <bits/stdc++.h>

using namespace std;

int ans = INT_MAX;

vector<int>id;
vector<int>pid;
vector<int>child;
unordered_map<int, int>hashTable;

void DFS(vector<bool>vis, int target, int i, int cost);

剩余50%内容，订阅会员后查看

STICK永久会员

打赏 收藏 海报 链接