1. Toy模板网首页
  2. > Toy博客

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

9月前 作者：FellAveal 分类：Toy博客 阅读(40) 违法举报

这篇具有很好参考价值的文章主要介绍了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

代码提交结果：

        提交了很多次，可算过了

本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地,数据结构,PTA,数据结构,算法

题目分析： 

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

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。所以在算法中加入判断一下即可(困扰了我很久的一个问题)。

本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地,数据结构,PTA,数据结构,算法

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

本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地,数据结构,PTA,数据结构,算法

        改后的代码见代码展示。 

 代码展示：

//
// 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;文章来源地址https://www.toymoban.com/news/detail-782053.html

到了这里，关于7-1 天梯地图 (PTA-数据结构)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构Pta训练题-编程2

    感谢你这么帅（漂亮）​还支持我 一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。 输入

    2024年02月16日
    浏览(49)
  • 7-1 抢红包(PTA - 数据结构)

    7-1 抢红包(PTA - 数据结构)

    没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。 输入格式： 输入第一行给出一个正整数N（≤104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

    2024年01月23日
    浏览(40)
  • 数据结构第6章练习答案（PTA）

    数据结构第6章练习答案（PTA）

    2-1具有5个顶点的有向完全图有多少条弧？（ C ） A.10        B.16        C.20        D.25 2-2关于图的邻接矩阵，下列哪个结论是正确的？（ B ） A.有向图的邻接矩阵总是不对称的 B.有向图的邻接矩阵可以是对称的，也可以是不对称的 C.无向图的邻接矩阵总是不对称的

    2024年02月05日
    浏览(42)
  • 数据结构Pta训练题函数题详解

    数据结构Pta训练题函数题详解

    感谢你这么帅（漂亮）​还支持我 pta网站：PTA | 程序设计类实验辅助教学平台 (pintia.cn) 文章内容较长，建议搭配目录使用 给定一个顺序存储的线性表，请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储，并且相对位置不能改变。 函数接

    2024年02月12日
    浏览(48)

  • 数据结构pta训练题-编程题1

    感谢你这么帅（漂亮）​还支持我 训练网站：PTA训练平台 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

    2024年02月10日
    浏览(39)
  • 数据结构第5章练习答案（PTA）

    数据结构第5章练习答案（PTA）

    2-1以下说法错误的是（ A ） A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种\\\"分支层次\\\"结构 E.任何只含一个结点的集合是一棵树 2-2利用二叉链表存储树，则根

    2024年02月04日
    浏览(48)
  • 数据结构第7~8章练习答案（PTA）

    数据结构第7~8章练习答案（PTA）

    2-1适用于折半查找的表的存储方式及元素排列要求为( D ) 。 A.链接方式存储，元素无序 B.链接方式存储，元素有序 C.顺序方式存储，元素无序 D.顺序方式存储，元素有序 2-2在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为

    2024年02月04日
    浏览(33)

  • 数据结构第1~2章练习答案（PTA）

    2-1下面代码段的时间复杂度是（ B ） A.O(n)                B.O(n²)                C.O(n³)                D.O(2ⁿ) 2-2下列函数的时间复杂度是（ B ） A.O(logn)           B.O()                C.O(n)                 D.O(nlogn)  2-3顺序表是线性表的( B ) A.链式

    2024年02月07日
    浏览(43)

  • 排序7-2 奥运排行榜 PTA 数据结构

    7-2 奥运排行榜 分数 25 全屏浏览题目 切换布局 作者 陈越 单位 浙江大学 每年奥运会各大媒体都会公布一个排行榜，但是细心的读者发现，不同国家的排行榜略有不同。比如中国金牌总数列第一的时候，中国媒体就公布“金牌榜”；而美国的奖牌总数第一，于是美国媒体就

    2024年02月02日
    浏览(46)

  • 7-1 回文判断（数据结构） PTA C语言

    回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。编写一个程序，使用栈判定给定的字符序列是否为回文。 若用C++，可借助STL的容器实现。 输入格式: 输入待判断的字符序列，按回车键结束，字符序列长度20。 输出格式: 若字符序列是

    2024年02月02日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包