题目粗心
现有N个节点和M条边的图，给定终点和起点，找出一条间隔最短的门路和一条耗时起码的门路。其规定如下：
- 1、对于有多条最短门路，找到耗时最短的
- 2、对于有多条耗时最短门路找到岔路口(顶点)起码的
- 3、如果最短门路和耗时起码门路一样，合并输入。
算法思路
此题为比拟惯例的最短门路问题，应用两次迪杰斯特拉算法就能够进行求解，第一次求解间隔最短的门路，应用间隔作为第一标尺，耗时作为第二标尺。第二次应用耗时最短的门路，应用耗时作为第一标尺，门路上的节点数目作为第二标尺。迪杰斯特拉算法的过程不再这里赘述。对于两条最短门路是否齐全一样的判断办法就是间接比拟前驱数组，从起点开始始终往前走，遇到不同的阐明是不同门路。
留神点
- 1、测试点4谬误的状况极有可能是在编写第二次迪杰斯特拉算法的时候复制了之前的代码导致有些变量的名字没有更改过去。
- 2、第二次应用迪杰斯特拉算法求解的时候得初始化visited数组。
提交后果
AC代码
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 501;int N, M;// 顶点和边的数目int Start, End;// 终点和起点bool visited[maxn];// 拜访标记数组// 间隔最短int L[maxn][maxn];// 每一对节点间的长度int disL[maxn]; // 每一个节点到终点的最短距离int preL[maxn]; // 求解最短距离门路中每一个节点的前驱节点// 耗时最短int T[maxn][maxn];// 每一对节点间的工夫int disT[maxn]; // 每一个节点到终点的最短耗时int preT[maxn]; // 求解最短耗时门路中每一个节点的前驱节点int num[maxn]; // 求解最短耗时门路中每一个节点到终点的最短节点数目void findShortestPath(int start) { fill(disL, disL + maxn, 0x3fffffff); fill(disT, disT + maxn, 0x3fffffff); disL[start] = 0; disT[start] = 0; for (int i = 0; i < N; ++i) { int minD = 0x3fffffff; int minIndex = -1; for (int j = 0; j < N; ++j) { if (!visited[j] && disL[j] < minD) { minD = disL[j]; minIndex = j; } } // 剩下的节点不连通 if (minIndex == -1) return; visited[minIndex] = true; // 依据minIndex更新disL数组 for (int j = 0; j < N; ++j) { if (!visited[j] && L[minIndex][j] != 0) { if (disL[j] > disL[minIndex] + L[minIndex][j]) { disL[j] = disL[minIndex] + L[minIndex][j]; disT[j] = disT[minIndex] + T[minIndex][j]; preL[j] = minIndex; } else if (disL[j] == disL[minIndex] + L[minIndex][j] && disT[j] > disT[minIndex] + T[minIndex][j]) { disT[j] = disT[minIndex] + T[minIndex][j]; preL[j] = minIndex; } } } }}void findFastestPath(int start) { fill(disT, disT + maxn, 0x3fffffff); fill(num, num + maxn, 0x3fffffff); disT[start] = 0; num[start] = 1; for (int i = 0; i < N; ++i) { int minD = 0x3fffffff; int minIndex = -1; for (int j = 0; j < N; ++j) { if (!visited[j] && disT[j] < minD) { minD = disT[j]; minIndex = j; } } // 剩下的节点不连通 if (minIndex == -1) return; visited[minIndex] = true; // 依据minIndex更新disT数组 for (int j = 0; j < N; ++j) { if (!visited[j] && T[minIndex][j] != 0) { if (disT[j] > disT[minIndex] + T[minIndex][j]) { disT[j] = disT[minIndex] + T[minIndex][j]; preT[j] = minIndex; num[j] = num[minIndex] + 1; } else if (disT[j] == disT[minIndex] + T[minIndex][j] && num[j] > num[minIndex] + 1) { preT[j] = minIndex; num[j] = num[minIndex] + 1; } } } }}// 判断最短距离和最短耗时门路是否一样bool isSame() { int t = End; while(preT[t]==preL[t]){ if(preT[t]==Start){ return true; } t = preT[t]; } return false;}// 输入最短门路void printPath(int end, int path[]) { if (Start == end) { printf("%d", Start); return; } printPath(path[end], path); printf(" -> "); printf("%d", end);}int main() { scanf("%d %d", &N, &M); int v1, v2, oneWay, length, time; for (int i = 0; i < M; ++i) { scanf("%d %d %d %d %d", &v1, &v2, &oneWay, &length, &time); L[v1][v2] = length; T[v1][v2] = time; if (oneWay == 0) { // 双向边 L[v2][v1] = length; T[v2][v1] = time; } } scanf("%d %d", &Start, &End); findShortestPath(Start); memset(visited, 0, sizeof(visited)); findFastestPath(Start); if (isSame()) { printf("Distance = %d; Time = %d: ", disL[End], disT[End]); printPath(End, preL); } else { printf("Distance = %d: ", disL[End]); printPath(End, preL); printf("\n"); printf("Time = %d: ", disT[End]); printPath(End, preT); } return 0;}