题目:
光明小学的小朋友们要举行一年一度的接力跑大赛了,但是小朋友们却遇到了一个难题:设计接力跑大赛的线路,你能帮助他们完成这项工作么?
光明小学可以抽象成一张有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。要求时间复杂度控制在O(N^3*log(M))。
map数组表示了一张稠密图,其中任意两个不同节点i,j间都有一条边,边的长度为map[i][j]。N表示其中的节点数。
你要返回的数组也必然是一个N * N的二维数组,表示从i出发走到j,经过M条边的最短路径
你的路径中应考虑包含重复边的情况。
参考:https://blog.csdn.net/u012465304/article/details/81180707
思路:其实就是M步无向图的最短路径遍历,设置步数为M,当M步到达所需要的end点且distance较小则更新,递归实现。
// Study.cpp: 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> #include <vector> #include <unordered_map> #include <unordered_set> #include <queue> #include <string> #include <algorithm> #include <sstream> #define INT_MAX 2147483647 // maximum (signed) int value #define INT_MIN (-2147483647 - 1) // minimum (signed) int value using namespace std; vector<vector<int>> result; vector<vector<int>> map; int minStep = INT_MAX; void dfs(int start, int end, int N ,int M ,int dis ,int steps) { if (steps == M) { //刚刚好 M步 到达所需要的end 且路径较短,则更新数值 if (start == end && dis < minStep) minStep = dis; return; } int rdis; for (int next = 0; next < N; next++) { if (next == start) continue; rdis = dis + map[start][next]; dfs(next, end, N, M, rdis,steps+1); } } vector<vector<int>> solution(int N, int M) { result = vector<vector<int>> (N, vector<int>(N, 0)); int dis = 0; queue<vector<int>> Que; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // 求从 i -> j 的最短路径 dfs(i, j, N, M, 0, 0); result[i][j] = minStep; minStep = INT_MAX; } } return result; } int main() { int N, M; cin >> N >> M; int tmp; map = vector<vector<int>> (N, vector<int>(N, 0)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> tmp; map[i][j] = tmp; } } solution(N, M); for (auto g : result) { for (auto i : g) cout << i << " "; cout << endl; } system("pause"); return 0; }