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

题目粗心

现有N个节点和M条边的图,给定终点和起点,找出一条间隔最短的门路和一条耗时起码的门路。其规定如下:

  • 1、对于有多条最短门路,找到耗时最短的
  • 2、对于有多条耗时最短门路找到岔路口(顶点)起码的
  • 3、如果最短门路和耗时起码门路一样,合并输入。

算法思路

此题为比拟惯例的最短门路问题,应用两次迪杰斯特拉算法就能够进行求解,第一次求解间隔最短的门路,应用间隔作为第一标尺,耗时作为第二标尺。第二次应用耗时最短的门路,应用耗时作为第一标尺,门路上的节点数目作为第二标尺。迪杰斯特拉算法的过程不再这里赘述。对于两条最短门路是否齐全一样的判断办法就是间接比拟前驱数组,从起点开始始终往前走,遇到不同的阐明是不同门路。

【腾讯云】云产品限时秒杀,爆款1核2G云服务器,首年99元

留神点

  • 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;
}

阿里云限时活动-2核2G-5M带宽-40-100G SSD服务器,特惠价86元/年(原价724元/年,限时99元续购三次),速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据