华为笔试题
第一道题比较简单,第二道第三道大家可以看一看。
第三道:
3.电车路线规划
为了方便城市居民有序流动,城市A开通了一系列有轨电车路线,每列电车会沿固定的路线
循环行驶,电车票价实行一票制,不论乘坐多少站,均按固定价格收费,循环坐车时不重复
收费。请计算你在城市里面,从出发点到目的地,乘坐电车的最低费用。
输入:
第一行:M X Y Z: M表示电车线路总数量,X表示初始化编号, Y表示终点编号,Z表示身上的
金钱数。1 <= M <= 50; 0 <= X, Y <= 500; X != Y; 1 <= Z <= 500。
第二行:price n station1 station2 station3 ... stationn 代表本条电车线路经过的站点
的站点编号。站点编号可能比站点总的数量大, 即stationn 可能大于n。
1 <= n <= 10; 0 <= stationn <= 500; 1 <= price <= 10;
第M+1行:price n station1 station2 station3 ... stationn
输出:
需要花费的金钱数。如果无法达到或身上的金钱数不够达到,返回-1;
输入:5 15 12 4
2 2 7 12
3 3 4 5 15
4 1 6
3 2 15 7
1 3 12 13 7
输出:4
第三道:
3.电车路线规划
为了方便城市居民有序流动,城市A开通了一系列有轨电车路线,每列电车会沿固定的路线
循环行驶,电车票价实行一票制,不论乘坐多少站,均按固定价格收费,循环坐车时不重复
收费。请计算你在城市里面,从出发点到目的地,乘坐电车的最低费用。
输入:
第一行:M X Y Z: M表示电车线路总数量,X表示初始化编号, Y表示终点编号,Z表示身上的
金钱数。1 <= M <= 50; 0 <= X, Y <= 500; X != Y; 1 <= Z <= 500。
第二行:price n station1 station2 station3 ... stationn 代表本条电车线路经过的站点
的站点编号。站点编号可能比站点总的数量大, 即stationn 可能大于n。
1 <= n <= 10; 0 <= stationn <= 500; 1 <= price <= 10;
第M+1行:price n station1 station2 station3 ... stationn
输出:
需要花费的金钱数。如果无法达到或身上的金钱数不够达到,返回-1;
输入:5 15 12 4
2 2 7 12
3 3 4 5 15
4 1 6
3 2 15 7
1 3 12 13 7
输出:4
全部评论
做不出来没关系,反正进池子也要泡半年
电车路线题本质是最短路,但华为非要用票价绕晕你
输出4?我怀疑是华为暗示“死”也要进池子
第三题我的思路是用dijkstra,先用哈希表来构建站点到编号的映射,再构建邻接表。对于同一条电车线路,例如A-B-C,构建(A,B),(A,C),(B,C)三条边,每条边都是同样的权重。但是最后时间不够了,不知道能AC不
相关推荐
土木小牛码:刚准备开骂了
点赞 评论 收藏
分享
09-24 17:40
门头沟学院 golang 点赞 评论 收藏
分享