关注
第二题:不知道能不能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;
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
转发
牛客热帖
- 1... 携程oc了2.3W
- 2... 美团-Java后端-平台技术部-一面凉经(复活赛)1.1W
- 3... 【话术建议】求职者和企业的互骗话术?6005
- 4... 捞简历这件事儿5247
- 5... 31天勇闯盲审(附盲审经验4772
- 6... 字节抖音电商后端日常实习一二三面已oc4586
- 7... 我真是一个废物,废物本废,到现在也找不到实习不管回答上来,还是没回答上来,都不会有公司要我的。。。。。。。好了,emo完了,继续努力,总有眼瞎面试官能看上我的叭3980
- 8... 微信支付二面3774
- 9... 问一下xdm 怎么把拒绝过的Offer 再舔回来🥺3008
- 10... 线程题2729
正在热议
# 牛客帮帮团来啦!有问必答 #
685822次浏览 11266人参与
# 市场营销面经 #
3954次浏览 114人参与
# 2022届毕业生现状 #
315504次浏览 4396人参与
# 你会选择考研还是直接就业 #
74637次浏览 854人参与
# 我的上岸简历长这样 #
160750次浏览 3213人参与
# 无实习如何秋招上岸 #
219558次浏览 3433人参与
# 浅聊一下我实习的辛苦费 #
79845次浏览 742人参与
# 你的简历改到第几版了 #
298852次浏览 4513人参与
# 投了多少份简历才上岸 #
55727次浏览 940人参与
# 软件开发投递记录 #
465757次浏览 7117人参与
# 运营面经 #
10474次浏览 261人参与
# 科大讯飞求职进展汇总 #
36058次浏览 365人参与
# Offer比较,你最看重什么? #
49434次浏览 479人参与
# 毕业后不工作的日子里我在做什么 #
51983次浏览 687人参与
# 夸夸我的求职搭子 #
63577次浏览 774人参与
# 租房前辈的忠告 #
32664次浏览 2067人参与
# 秋招开了,你想投哪些公司呢 #
116214次浏览 3241人参与
# 硬件人的简历怎么写 #
77263次浏览 780人参与
# 写简历别走弯路 #
285946次浏览 3514人参与
# 产品面经 #
22119次浏览 426人参与