关注
第二题:不知道能不能100%
int func(vector<vector<int>>& nums, int city) {
if (nums.empty() || city == 0) return -1;
int size = nums.size();
vector<vector<long long>> matrix(city, vector<long long>(city, INT_MAX)); //初始化为正无穷,使用int,会导致数据溢出。
for (int i = 0; i < city; ++i)
matrix[i][i] = 0;
for (int i = 0; i < size; ++i) {
int x = nums[i][0];
int y = nums[i][1];
int distance = nums[i][2];
matrix[x][y] = distance;
matrix[y][x] = distance;
}
for (int k = 0; k < city; ++k) {
for (int i = 0; i < city; ++i) {
for (int j = 0; j < city; ++j) {
if (matrix[i][j] > matrix[i][k] + matrix[k][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
int sum = INT_MAX;
int res = city;
for (int i = 0; i < city; ++i) {
int tmp = 0;
for (int j = 0; j < city; ++j) {
tmp += matrix[i][j];
cout << matrix[i][j] << " ";
}
cout << endl;
if (tmp < sum) {
sum = tmp;
res = i;
}
}
return res == city ? -1 : res;
}
查看原帖
点赞 评论
相关推荐
05-25 15:05
长沙理工大学 计算机类 点赞 评论 收藏
转发
点赞 评论 收藏
转发
牛客热帖
正在热议
# 和牛牛一起刷题打卡 #
8506次浏览 782人参与
# 机械制造薪资爆料 #
346559次浏览 4082人参与
# 牛客帮帮团来啦!有问必答 #
1042625次浏览 15864人参与
# 通信硬件薪资爆料 #
248889次浏览 2344人参与
# 你收到了团子的OC了吗 #
523133次浏览 6216人参与
# 你怎么评价今年的春招? #
8204次浏览 147人参与
# 本周投递记录 #
217094次浏览 5328人参与
# 晒一晒我的offer #
3709055次浏览 57430人参与
# 腾讯工作体验 #
150125次浏览 1458人参与
# 担心入职之后被发现很菜怎么办 #
36248次浏览 306人参与
# 春招你拿到offer了吗 #
396628次浏览 5729人参与
# Offer比较,求稳定还是求发展 #
6549次浏览 82人参与
# 百度工作体验 #
28345次浏览 285人参与
# 设计人如何选offer #
14412次浏览 281人参与
# 我想象的工作vs实际工作 #
103638次浏览 1673人参与
# 来选选带哪个offer回家过年 #
190708次浏览 1829人参与
# 实习生应该准时下班吗 #
86986次浏览 643人参与
# 我发现了面试通关密码 #
375792次浏览 6958人参与
# 如何写一份好简历 #
307842次浏览 4395人参与
# 字节跳动工作体验 #
72715次浏览 2005人参与