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%的样例。有无大佬指点一波。

#笔经##vivo##笔试题目#
全部评论
应该是每个节点找它所有前驱节点的最大值 或者你一开始就把边反着连
2 回复 分享
发布于 2021-06-19 14:13
我的理解是拓扑排序求最长路径,不知道理解的对不对==
点赞 回复 分享
发布于 2021-06-20 23:36
甘帝么
点赞 回复 分享
发布于 2021-06-20 21:37
第一题不知道为啥只能过30%
点赞 回复 分享
发布于 2021-06-20 14:29

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
点赞 评论 收藏
分享
评论
点赞
7
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务