PTA数据结构与算法题目集(中文) 7-9

7-9 旅游规划 (25 分)

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式:

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

输出样例:

3 40

题目分析:一道图的Dijkstra算法基本题 注意本题中不需要输出 最短路径的顺序 所以不需要记录路径的Path数组 需要记录源点到目标点的路径长度Dist数组 还要注意决定路径的是长度和价格两个因素 所以再判断完长度后要判断价格 如果因素更多，要增加更多的判断

 #define _CRT_SECURE_NO_WARNINGS

 #include<stdio.h>

 #include<stdlib.h>

 #include<malloc.h>

 #define MAXVERTEXNUM 500

 #define INIFITY 65535

 typedef struct ENode* Edge;

 struct ENode

 {

     int V1, V2;

     int Length;

     int Weight;

 };

 typedef struct EleNode

 {

     int Length;

     int Weight;

 }ElementType;

 typedef struct GNode* Graph;

 struct GNode

 {

     int Nv;

     int Ne;

     ElementType G[MAXVERTEXNUM][MAXVERTEXNUM];

 };

 Graph BuildGraph(int VertexNum)

 {

     Graph Gra = (Graph)malloc(sizeof(struct GNode));

     Gra->Nv = VertexNum;

     Gra->Ne = ;

     for(int i=;i<Gra->Nv;i++)

         for (int j = ; j < Gra->Nv; j++)

         {

             if (i == j)

             {

                 Gra->G[i][j].Length = ;

                 Gra->G[i][j].Weight = ;

             }

             else

             {

                 Gra->G[i][j].Length = INIFITY;

                 Gra->G[i][j].Weight = INIFITY;

             }

         }

     return Gra;

 }

 void Insert(Edge E, Graph Gra)

 {

     Gra->G[E->V1][E->V2].Length = E->Length;

     Gra->G[E->V1][E->V2].Weight = E->Weight;

     Gra->G[E->V2][E->V1].Length = E->Length;

     Gra->G[E->V2][E->V1].Weight = E->Weight;

 }

 Graph CreateGraph(int N,int M)

 {

     Edge E = (Edge)malloc(sizeof(struct ENode));

     Graph Gra = BuildGraph(N);

     Gra->Ne = M;

     for (int i = ; i < Gra->Ne; i++)

     {

         scanf("%d%d%d%d", &(E->V1), &(E->V2), &(E->Length), &(E->Weight));

         Insert(E, Gra);

     }

     return Gra;

 }

 int Dist[MAXVERTEXNUM];

 int Price[MAXVERTEXNUM];

 int Collected[MAXVERTEXNUM];

 int FindMin(Graph G)

 {

     int MinDist= INIFITY;

     int Min = -;

     for (int i = ; i < G->Nv; i++)

     {

         if (!Collected[i] && Dist[i] < MinDist)

         {

             MinDist = Dist[i];

             Min = i;

         }

     }

     return Min;

 }

 void Dijkstra(Graph Gra, int V)

 {

     for (int i = ; i < Gra->Nv; i++)

     {

         Dist[i] = Gra->G[V][i].Length;

         Price[i] = Gra->G[V][i].Weight;

     }

     Collected[V] = ;

     while ()

     {

         int Min = FindMin(Gra);

         if (Min == -)

             break;

         for (int i = ; i < Gra->Nv; i++)

         {

             if (!Collected[i]&&Dist[Min] + Gra->G[Min][i].Length < Dist[i])

             {

                 Dist[i] = Dist[Min] + Gra->G[Min][i].Length;

                 Price[i] = Price[Min] + Gra->G[Min][i].Weight;

             }

             else if (!Collected[i]&&Dist[Min] + Gra->G[Min][i].Length == Dist[i] && Price[Min] + Gra->G[Min][i].Weight < Price[i])

             {

                 Price[i] = Price[Min] + Gra->G[Min][i].Weight;

             }

         }

         Collected[Min] = ;

     }

 }

 int main()

 {

     int N, M,S,D;

     scanf("%d%d%d%d", &N, &M, &S, &D);

     Graph G = CreateGraph(N, M);

      Dijkstra(G, S);

     printf("%d %d", Dist[D],Price[D]);

     return ;

 }

巴特西

PTA数据结构与算法题目集(中文) 7-9

PTA数据结构与算法题目集(中文) 7-9

输入格式:

输出格式:

输入样例:

输出样例:

最新文章

热门文章