7-1 天梯地图 (PTA-数据结构)

本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

输入格式：

输入在第一行给出两个正整数N（2?≤?N?≤?500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：

V1 V2 one-way length time

其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。

输出格式：

首先按下列格式输出最快到达的时间T和用节点编号表示的路线：

Time = T: 起点 => 节点1 => ... => 终点

然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：

Distance = D: 起点 => 节点1 => ... => 终点

如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。

如果这两条路线是完全一样的，则按下列格式输出：

Time = T; Distance = D: 起点 => 节点1 => ... => 终点

输入样例1：

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
5 4 0 2 3
5 9 1 1 4
0 6 0 1 1
7 3 1 1 2
8 3 1 1 2
2 5 0 2 2
2 1 1 1 1
1 5 0 1 3
1 4 0 1 1
9 7 1 1 3
3 1 0 2 5
6 3 1 2 1
5 3

输出样例1：

Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3

输入样例2：

7 9
0 4 1 1 1
1 6 1 3 1
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 3 1
3 2 1 2 1
4 5 0 2 2
6 5 1 2 1
3 5

输出样例2：

Time = 3; Distance = 4: 3 => 2 => 5

---

代码提交结果：

? ? ? ? 提交了很多次，可算过了

---

题目分析：?

? ? ? ? 作为这次图的作业中的第一道题，题目的长度和输入的内容，非常劝退，这里我建议先从输入下手（先去存，从主函数的输入开始），进行数据的存入。

1.设计输入

? ? ? ? 输入要求是存入一个地图，并且为有向的，所以这里第一时间想到用矩阵存（即二维数组），并且以二维数组的两个下标表示点与点之间是否有连接（比如e[x][y]表示x到y），并给每个点设置两个变量（用结构体实现），即路程和时间。输入定义点的数量，边的数量，将边的信息循环写入二维数组，要注意若两个点之间没有连接，需要将其初始化为MAX或其他内容。之后是两个整型变量，起点和终点，下面是这里内容的代码实现（此处还是比较简单的）：

#define MAX 32767
typedef struct Edge{
    int length;
    int time;
}Edge;

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    Edge e[n][n];
    for(int i = 0;i<n;i++){
        for (int j = 0; j < n; ++j) {
            e[i][j].time = MAX;
            e[i][j].length = MAX;
        }
    }
    for(int i = 0;i<m;i++){
        int flag = -1;
        int x,y,len,times;
        scanf("%d %d %d %d %d",&x,&y,&flag,&len,&times);
        e[x][y].length = len;
        e[x][y].time = times;
        if(flag == 0){
            e[y][x].length = len;
            e[y][x].time = times;
        }
    }
    int start,finish;
    scanf("%d %d",&start,&finish);

    //......
    //......
}

?2.算法选择

? ? ? ? 很明显，题目要求求出最小的“距离”（这里的“距离”包括上文所提的路程和时间，下文只会使用这三个名词，防止混淆），这里需要选择一种算法来实现要求，这里考虑到“距离”或是权值，应当想到两种算法，一种是普利姆算法（或是克鲁斯卡尔算法），一种是迪杰斯特拉算法（弗洛伊德算法求多个点到多个点的路径长度，这道题没必要使用）。经过思考，前者求最小生成树，并未能得到一个点到其他各点的最小距离，所以选择后者。由于是两个变量，所以分开求解。

? ? ? ? 根据上课所学，和老师ppt中给到的代码，我们不难copy出（算法实现过程暂时不在此说明，日后会写的）：

#define MAX 32767
typedef struct {
    int pernode;
    int pathlength;
}ShortestPath;

void DIJ_ShortestDistance(int v,int n,Edge edge[n][n],ShortestPath sp[n]) {
    int i, j, m, k, min;
    int flag[n];
    for (int jj = 0; jj < n; jj++) {
        flag[jj] = 0;
    }
    flag[v] = 1;
    for (i = 0; i < n; i++) {
        sp[i].pathlength = edge[v][i].length;
        if ((sp[i].pathlength != 0) && (sp[i].pathlength != MAX))
            sp[i].pernode = v;
    }
    for (i = 0; i < n; i++) {
        min = MAX;
        for (j = 0; j < n; j++) {
            if ((flag[j] == 0) && (sp[j].pathlength < min)) {
                min = sp[j].pathlength;
                m = j;
            }
        }
        flag[m] = 1;
        for (k = 0; k < n; k++) {
            if((flag[k]==0)&&((sp[m].pathlength + edge[m][k].length)<sp[k].pathlength)) {
                sp[k].pathlength = sp[m].pathlength + edge[m][k].length;
                sp[k].pernode = m;
            }
        }
    }
}

void DIJ_ShortestTime(int v,int n,Edge edge[n][n],ShortestPath sp[n]) {
    int i, j, m, k, min;
    int flag[n];
    for (int jj = 0; jj < n; jj++) {
        flag[jj] = 0;
    }
    flag[v] = 1;
    for (i = 0; i < n; i++) {
        sp[i].pathlength = edge[v][i].time;
        if ((sp[i].pathlength != 0) && (sp[i].pathlength != MAX))
            sp[i].pernode = v;
    }
    for (i = 0; i < n; i++) {
        min = MAX;
        for (j = 0; j < n; j++) {
            if ((flag[j] == 0) && (sp[j].pathlength < min)) {
                min = sp[j].pathlength;
                m = j;
            }
        }
        flag[m] = 1;
        for (k = 0; k < n; k++) {
            if((flag[k]==0)&&((sp[m].pathlength + edge[m][k].time)<sp[k].pathlength)) {
                sp[k].pathlength = sp[m].pathlength + edge[m][k].time;
                sp[k].pernode = m;
            }
        }
    }
}

? ? ? ? 通过这两个函数的实现，我们可以求得起点到每个点的最短距离，?但是，题目中输出还有要求：输出路线，并且“如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的”。这些要求比较为难，咱们先跳过，先实现最基本的解决。

---

3.保证输出

? ? ? ? 题目要求的输出有：最短距离，最短距离的路线。

? ? ? ? 最短距离只需要打印上面迪杰斯特拉算法构建好的到每个点最短距离的数组中，起点到终点的最短距离（虽然这个算法将到每个点的最短距离的长度全算出来了）。至于最短距离的路线，我们可以巧妙地看到，上面算法也写到了每个点在起点到该点的最短距离的路线中的前一个点（pernode），这样，我们可以从终点，根据前一个点是谁，稳妥的一直摸到起点（即到达终点的时候break）。

? ? ? ? 思路有了，开始准备储存，这里储存思路就是创建一个一维数组，去存每个点，存储方式看代码不难理解（这里我有个思路是倒序存，正序读，但是没有被成功实现），选择了正序存，倒序读的思路，这里需要设置两个flag记录多少位，方便读取的时候倒序读到下标为0。后面再写一个字符串比较的函数（strcmp要求字符串char类型，所以需要自己写），进行选择性输出。下面是代码：

int StringCmp(int c1[],int c2[],int c1len,int c2len){
    if(c1len != c2len)
        return 0;
    else{
        for(int i = 0;i<c1len;i++){
            if(c1[i]!=c2[i])
                return 0;
        }
        return 1;
    }
}

int main(){
    //...
    //...
    int distances[n],times[n];
    for(int i = 0;i<n;i++){
        distances[i] = -1;
        times[i] = -1;
    }
    int disflag = 0;
    int timeflag = 0;
    distances[0] = finish ;

    for(int i = 1;;i++){
        distances[i] = distance[distances[i-1]].pernode;
        disflag++;
        if(distances[i] == start)
            break;
    }
    times[0] = finish;
    for(int i = 1;;i++){
        times[i] = time[times[i-1]].pernode;
        timeflag++;
        if(times[i] == start)
            break;
    }
    if(StringCmp(distances,times,disflag,timeflag) != 0){
        printf("Time = %d; ", time[finish].pathlength);
        printf("Distance = %d:", distance[finish].pathlength);
        for (int i = disflag; i >= 0; i--) {
            if (i != 0)
                printf(" %d =>", distances[i]);
            else
                printf(" %d", distances[i]);
            if (distances[i] == finish)
                break;
        }
    }
    else {
        printf("Time = %d:", time[finish].pathlength);
        for (int i = timeflag; i >= 0; i--) {
            if (i != 0)
                printf(" %d =>", times[i]);
            else
                printf(" %d", times[i]);
            if (times[i] == finish)
                break;
        }
        printf("\n");
        printf("Distance = %d:", distance[finish].pathlength);
        for (int i = disflag; i >= 0; i--) {
            if (i != 0)
                printf(" %d =>", distances[i]);
            else
                printf(" %d", distances[i]);
            if (distances[i] == finish)
                break;
        }
    }

}

---

4.调整改造

? ? ? ? 至此，我们的程序已经写的差不多了，但是只能过几个检测点，不能全对，原因就在于没有去满足输出条件：“如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的”。顾名思义，我们需要在咱们的迪杰斯特拉算法代码里面去改这里我们需要捋一捋思路去满足这个要求。

? ? ? ? 第一个条件，最快路径。要在最快相同时候去找最短距离的路，即通过距离短的结点。l例如下图，2到4和3到4的距离和时间相等，1到2时间1，长度2，1到3的时间1，长度1，那么如果要去找1到4的最短时间距离，就应该去走134，而不是124。所以在算法中加入判断一下即可(困扰了我很久的一个问题)。

? ? ? ? ?第二个条件，最短路程。要求过结点最少，就要求在执行的时候记住所访问过的结点数，判断当两条路相等的时候，如果此时遍历到的结点到起点的结点数小于先前的那个结点到起点的结点数，就进行更新prenode操作。

? ? ? ? 改后的代码见代码展示。?

---

?代码展示：

//
// Created by DDD on 2023/12/10.
//
#include <stdio.h>
#include <string.h>

#define MAX 32767
typedef struct Edge{
    int length;     //路程
    int time;       //时间
}Edge;

typedef struct {
    int pernode;            //前一个结点
    int pathlength;         //路径长度
}ShortestPath;

void DIJ_ShortestDistance(int v,int n,Edge edge[n][n],ShortestPath sp[n]) {
    int i, j, m, k, min;
    int flag[n+1];              //终点集检查，0为非终点集内元素
    int num[n+1];               //此路线经过的点
    for (int jj = 0; jj < n; jj++) {
        flag[jj] = 0;
        num[jj] = 0;
    }
    num[v] = 1;
    flag[v] = 1;
    for (i = 0; i < n; i++) {
        sp[i].pathlength = edge[v][i].length;
        if ((sp[i].pathlength != 0) && (sp[i].pathlength != MAX))
            sp[i].pernode = v;
    }
    for (i = 0; i < n; i++) {
        min = MAX;
        for (j = 0; j < n; j++) {
            if ((flag[j] == 0) && (sp[j].pathlength < min)) {
                min = sp[j].pathlength;     //找第一个最小的，列到终点集
                m = j;
            }
        }
        flag[m] = 1;                        //进入终点集
        for (k = 0; k < n; k++) {           //以这个点为基准，更新其他点的最短距离
            if((flag[k]==0)&&((sp[m].pathlength + edge[m][k].length)<sp[k].pathlength)) {
                sp[k].pathlength = sp[m].pathlength + edge[m][k].length;
                sp[k].pernode = m;
                num[k] = num[m] + 1;
            }
            else if((flag[k]==0)&&((sp[m].pathlength + edge[m][k].length)==sp[k].pathlength)){
                if(num[m] + 1 < num[k]){        //相等时，比较通过结点数
                    num[k] = num[m] + 1;
                    sp[k].pernode = m;
                }
            }
        }
    }
}

void DIJ_ShortestTime(int v,int n,Edge edge[n][n],ShortestPath sp[n]) {
    int i, j, m, k, min;
    int flag[n+1];
    for (int jj = 0; jj < n; jj++) {
        flag[jj] = 0;
    }
    flag[v] = 1;        //1为已经判断过，即加入终点集
    for (i = 0; i < n; i++) {
        sp[i].pathlength = edge[v][i].time;
        if ((sp[i].pathlength != 0) && (sp[i].pathlength != MAX))
            sp[i].pernode = v;
    }
    for (i = 0; i < n; i++) {
        min = MAX;
        for (j = 0; j < n; j++) {
            if ((flag[j] == 0) && (sp[j].pathlength < min)) {
                min = sp[j].pathlength;
                m = j;
            }
        }
        flag[m] = 1;
        for (k = 0; k < n; k++) {
            for (k = 0; k < n; k++) {
                if((flag[k]==0)&&((sp[m].pathlength + edge[m][k].time)<sp[k].pathlength)) {
                    sp[k].pathlength = sp[m].pathlength + edge[m][k].time;
                    sp[k].pernode = m;
                }
                else if((flag[k]==0)&&(sp[m].pathlength + edge[m][k].time) == sp[k].pathlength){
                    if(edge[sp[k].pernode][k].length  > edge[m][k].length)      //时间相等，前一个点到它的距离大于这个点到它距离
                        sp[k].pernode = m;                                      //更新
                }
            }
        }
    }
}

int StringCmp(int c1[],int c2[],int c1len,int c2len){
    if(c1len != c2len)
        return 0;
    else{
        for(int i = 0;i<c1len;i++){
            if(c1[i]!=c2[i])
                return 0;
        }
        return 1;
    }
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    Edge e[n][n];
    for(int i = 0;i<n;i++){
        for (int j = 0; j < n; ++j) {
            e[i][j].time = MAX;
            e[i][j].length = MAX;
        }
    }
    for(int i = 0;i<m;i++){
        int flag = -1;
        int x,y,len,times;
        scanf("%d %d %d %d %d",&x,&y,&flag,&len,&times);
        e[x][y].length = len;
        e[x][y].time = times;
        if(flag == 0){
            e[y][x].length = len;
            e[y][x].time = times;
        }
    }
    int start,finish;
    scanf("%d %d",&start,&finish);
    ShortestPath distance[n],time[n];
    int distances[n],times[n];
    for(int i = 0;i<n;i++){
        distances[i] = -1;
        times[i] = -1;
    }

    DIJ_ShortestDistance(start, n, e, distance);
    DIJ_ShortestTime(start,n,e,time);
    int disflag = 0;
    int timeflag = 0;
    distances[0] = finish ;

    for(int i = 1;;i++){
        distances[i] = distance[distances[i-1]].pernode;
        disflag++;
        if(distances[i] == start)
            break;
    }
    times[0] = finish;
    for(int i = 1;;i++){
        times[i] = time[times[i-1]].pernode;
        timeflag++;
        if(times[i] == start)
            break;
    }
    if(StringCmp(distances,times,disflag,timeflag) != 0){
        printf("Time = %d; ", time[finish].pathlength);
        printf("Distance = %d:", distance[finish].pathlength);
        for (int i = disflag; i >= 0; i--) {
            if (i != 0)
                printf(" %d =>", distances[i]);
            else
                printf(" %d", distances[i]);
            if (distances[i] == finish)
                break;
        }
    }
    else {
        printf("Time = %d:", time[finish].pathlength);
        for (int i = timeflag; i >= 0; i--) {
            if (i != 0)
                printf(" %d =>", times[i]);
            else
                printf(" %d", times[i]);
            if (times[i] == finish)
                break;
        }
        printf("\n");
        printf("Distance = %d:", distance[finish].pathlength);
        for (int i = disflag; i >= 0; i--) {
            if (i != 0)
                printf(" %d =>", distances[i]);
            else
                printf(" %d", distances[i]);
            if (distances[i] == finish)
                break;
        }
    }
}

---

回顾反思：

? ? ? ? 其中检查点有：所给样例，最小输入，检查最小时间路径，最大输出同时检查最小距离路径。

? ? ? ? 这道题难度在于迪杰斯特拉算法的思路，以及为了满足题目需求进行调整更改。总之还是需要好好地学一下这些算法是怎么运行的，尽量会写能写吧。

---

return 0;