网易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-tiezi15
电脑端请微信扫码>>
多说无益,直接上资料截图
每个方向专栏售价69元,但是参与2人组团就可免费领取!
点击马上领取>>https://www.nowcoder.com/link/campus_ziliao2024-tiezi15