2019阿里校招测评题，光明小学完全图最短路径问题 - 好文

光明小学的小朋友们要举行一年一度的接力跑大赛了，但是小朋友们却遇到了一个难题：设计接力跑大赛的线路，你能帮助他们完成这项工作么？
光明小学可以抽象成一张有N个节点的图，每两点间都有一条道路相连。光明小学的每个班都有M个学生，所以你要为他们设计出一条恰好经过M条边的路径。
光明小学的小朋友们希望全盘考虑所有的因素，所以你需要把任意两点间经过M条边的最短路径的距离输出出来以供参考。

你需要设计这样一个函数：
res[][] Solve( N, M, map[][]);
注意：map必然是N * N的二维数组，且map[i][j] == map[j][i]，map[i][i] == 0，-1e8 <= map[i][j]
<= 1e8。（道路全部是无向边，无自环）2 <= N <= 100, 2 <= M <= 1e6。

map数组表示了一张稠密图，其中任意两个不同节点i,j间都有一条边，边的长度为map[i][j]。N表示其中的节点数。
你要返回的数组也必然是一个N * N的二维数组，表示从i出发走到j，经过M条边的最短路径
你的路径中应考虑包含重复边的情况。

样例：

N = 3
M = 2
map = {
{0, 2, 3},
{2, 0, 1},
{3, 1, 0}
}

输出结果result为：
result = {
{4, 4, 3},
{4, 2, 5},
{3, 5, 2}
}

输入样例：

3
2
3 3
0 2 3
2 0 1
3 1 0

输出样例：

[[4, 4, 3],

[4, 2, 5],

[3, 5, 2]]

这是我在C下面用dfs写的代码，没用用剪枝，是一个非常暴力的dfs，看到网上有一个Python的答案是错的，所以自己写了一个，但是考的时候时间太短了没写完，是下来写的。

这个测评对面试、笔试没有任何影响，没写出来也没关系，但是大家还是不要直接复制黏贴我的，万一别人做个查重，你们所有人都复制黏贴我的会被发现的。

主要就是我不写出来不开心，所以自己下来写了。。。。。。。。。
#include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h>
#include <assert.h> #include <limits.h> #include <stdbool.h> /* 输入样例： 3 2 3 3
0 2 3 2 0 1 3 1 0 输出样例： [[4, 4, 3], [4, 2, 5], [3, 5, 2]] */ /**
请完成下面这个函数，实现题目要求的功能 **/ /** 当然，你也可以不按照这个模板来作答，完全按照自己的想法来 ^-^ **/ #define maxVal
100000 void dfs(const long N, const long M, const int target,long *maxDis,
long** map, int step, int thisPoint, int nowDis) { if (step == M) { if
(thisPoint == target) { if (nowDis < *maxDis) { *maxDis = nowDis; } } return; }
for (int nextPoint = 0; nextPoint < N; nextPoint++) { if (nextPoint !=
thisPoint) { dfs(N, M, target, maxDis, map, ++step, nextPoint, nowDis +
map[thisPoint][nextPoint]); step--; } } } long** Solve(long N, long M, int
map_size_row, int map_size_cols, long** map, int* result_size_rows, int*
result_size_cols) { long** res = (long**)malloc(map_size_row*sizeof(long*));
int _map_init_i = 0; for (_map_init_i = 0; _map_init_i<map_size_row;
++_map_init_i) { res[_map_init_i] = (long*)malloc(map_size_row*(sizeof(long)));
} for (int j = 0; j < map_size_cols; j ++) for (int i = j; i < map_size_row;
i++) { long maxDis = maxVal; dfs(N, M, i, &maxDis, map, 0, j, 0); res[j][i] =
maxDis; res[i][j] = maxDis; } *result_size_rows = map_size_row;
*result_size_cols = map_size_cols; return res; } int main() { int
res_size_rows, res_size_cols; long** res; long _N; scanf_s("%ld", &_N); long
_M; scanf_s("%ld", &_M); int _map_rows = 0; int _map_cols = 0; scanf_s("%d",
&_map_rows); scanf_s("%d", &_map_cols); long** _map =
(long**)malloc(_map_rows*sizeof(long*)); int _map_init_i = 0; for (_map_init_i
= 0; _map_init_i<_map_rows; ++_map_init_i) { _map[_map_init_i] =
(long*)malloc(_map_cols*(sizeof(long))); } int _map_i, _map_j; for (_map_i = 0;
_map_i < _map_rows; _map_i++) { for (_map_j = 0; _map_j < _map_cols; _map_j++)
{ long _map_item; scanf_s("%ld", &_map_item); _map[_map_i][_map_j] = _map_item;
} } res = Solve(_N, _M, _map_rows, _map_cols, _map, &res_size_rows,
&res_size_cols); int res_i, res_j; for (res_i = 0; res_i < res_size_rows;
res_i++) { for (res_j = 0; res_j < res_size_cols; res_j++) { printf("%ld ",
res[res_i][res_j]); } printf("\n"); } return 0; }
求点赞~~~

热门工具换一换