首页 > 2021vivo提前批笔试,第三题求教
头像
yunplayer
编辑于 2021-06-19 16:47
+ 关注

2021vivo提前批笔试,第三题求教

第三题:最短路径
图像从传感器到输出JPEG格式图片经过很多node处理,这些node构成一个图像处理的pipeline,其中的有些节点依赖于其他节点输出。A->B表示B的执行依赖于A。
假设每个node执行时间为A(t),即node A需要执行t秒,没有依赖的node可以并行执行。编写一个方法输入一个有向无环图pipeline,输出执行完需要的最短时间。
输入:第一行输入node的执行时间,第二行输入node的依赖关系。
输出:最短时间。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 100010;
int e[N], ne[N], h[N], w[N], idx;

// 拉链法建图
void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

// dfs深搜
int dfs(int u){
    int s = 0;
    //遍历u结点的所有儿子
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        s = max(s, dfs(j)); // 递归求所有儿子中值最大的那个
    }
    return s + w[u]; // 返回儿子最大值+本身的消耗
}

int main(){
    memset(h, -1, sizeof h);
    int num, k = 0;
    
    // 写入结点权重
    while(cin >> num){
        w[++ k] = num;
        if(cin.get() == '\n') break;
    }
    
    vector<bool> st(k); // 记录该节点是否有父结点
    k = 1;
    while(cin >> num){
        add(k, num);
        st[num] = true;
        char op = cin.get();
        if(op == ';') k++;
        else if(op == '\n') break;
    }

    // dfs,从每个根节点往下递归
    int ans = 0;
    for(int i = 1; i <= st.size(); i++){
        if(st[i] == false)
            ans += dfs(i);
    }
    
    cout << ans;
    
    return 0;
}
我的思路是这样的:从每个根节点递归往下搜,找到每个结点所有儿子中消耗最大的值,将最大值+该结点的消耗作为返回值,这样就能知道根节点的消耗了。不知道哪里有问题,只过了70%的样例。有无大佬指点一波。

全部评论

(4) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐