关于c++:PAT甲级1111-Online-Map

题目粗心

现有 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;
}