第二题:不知道能不能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; }
点赞 评论

相关推荐

头像
04-29 10:53
已编辑
东北大学 自动化类
点赞 评论 收藏
转发
牛客网
牛客企业服务