网易25届校招笔试真题&软件开发一二面经

仓库配送

【题目描述】

网易严选建有N个自营仓分布在全国各地,标记为仓库1到N。

给定一个配货时间组(v,u,w),v为出发仓库,u为目标仓库,w为从出发仓库到目标仓库的耗时时间。可能存在仓库间过远,无法支持调拨转货。

指定一个出发仓库K,我们需要将供应商发送到K仓库的货配送到各个仓库。问配送到所有可到达仓库所要最短时间?如果无法全部调拨到,则返回-1。

输入描述:

第一行三个正整数,由空格分割,分别表示仓库个数N,出发仓K,以及配送时间组个数M

接下来 M行,每行三个整数,由空格分割,分别表示(v,u,w)三个数,v为出发仓库,u为目标仓库,w为从出发仓库到目标仓库的耗时时间

输出描述:

一行一个数字表示答案,配送到所有可达仓库到最短时间

备注:

N的区间是[1, 100] ;

K的区间是[1, N] ;

times的最大长度是[1, 6000] ;

所有边 times[i] = (u, v, w),1<=u, v <= N 0 <= w <= 100

输入样例:

6 2 5

2 1 1

2 6 2

1 3 3

3 4 1

6 5 2

输出样例:

5

说明:

由图可知,所需最短时间为1+3+1=5

【解题思路】

最短路问题,floyd或者dijkstra都可以

【参考代码】

int floyd(vector<vector<int>>& graph, int N, int source)

{

for (int k = 1; k <= N; ++k) {

for (int i = 1; i <= N; ++i) {

for (int j = 1; j <= N; ++j) {

if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX)

graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

}

}

}

int ans = INT_MIN;

for (int i = 1; i <= N; ++i) {

ans = max(ans, graph[source][i]);

}

if (ans == INT_MAX)return -1;

return ans;

}

int main()

{

int N, K, M, v, u, w;

cin >> N >> K >> M;

vector<vector<int>> graph(N + 1, vector<int>(N + 1, INT_MAX));

for (int i = 0; i < M; ++i) {

cin >> v >> u >> w;

graph[v][u] = w;

}

for (int i = 0; i < N; ++i) {

graph[i][i] = 0;

}

cout << floyd(graph, N, K);

return 0;

}

......

资料全部内容请看《2025届求职宝典-理工科版

不收费,2人组团即可免费领取!已经发出10000份,涵盖各大公司求职资料,助你事半功倍!

资料包含:

  • 30+大厂面试真题+解析
  • 软件方向:阿里、腾讯、百度、小米、华为、美团......
  • 硬件方向:华为、比亚迪、汇川、新华三、中兴、海康威视......
  • 机械方向:比亚迪、华为、美的、长江存储、宁德时代......
  • 30+大厂岗位薪资爆料
  • 30+大厂offer攻略

拿offer,别犹豫,点击马上领取>>https://www.nowcoder.com/link/campus_ziliao2024-0604115

电脑端请微信扫码>>

多说无益,直接上资料截图

每个方向专栏售价69元,但是参与2人组团就可免费领取

点击马上领取>>https://www.nowcoder.com/link/campus_ziliao2024-0604115

全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
点赞 评论 收藏
分享
05-30 12:03
山西大学 C++
offer来了我跪着...:不是骗子,等到测评那一步就知道为啥这么高工资了
点赞 评论 收藏
分享
评论
6
9
分享

创作者周榜

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