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

7-9 旅游规划 (25 分)

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

输入格式:

输入说明：输入数据的第1行给出4个正整数

输出格式:

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

输入样例:

输出样例:

3 40

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

  1 #define _CRT_SECURE_NO_WARNINGS   
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<malloc.h>
  5 #define MAXVERTEXNUM 500
  6 #define INIFITY 65535
  7 
  8 typedef struct ENode* Edge;
  9 struct ENode
 10 {
 11     int V1, V2;
 12     int Length;
 13     int Weight;
 14 };
 15 
 16 typedef struct EleNode
 17 {
 18     int Length;
 19     int Weight;
 20 }ElementType;
 21 
 22 typedef struct GNode* Graph;
 23 struct GNode
 24 {
 25     int Nv;
 26     int Ne;
 27     ElementType G[MAXVERTEXNUM][MAXVERTEXNUM];
 28 };
 29 
 30 Graph BuildGraph(int VertexNum)
 31 {
 32     Graph Gra = (Graph)malloc(sizeof(struct GNode));
 33     Gra->Nv = VertexNum;
 34     Gra->Ne = 0;
 35     for(int i=0;i<Gra->Nv;i++)
 36         for (int j = 0; j < Gra->Nv; j++)
 37         {
 38             if (i == j)
 39             {
 40                 Gra->G[i][j].Length = 0;
 41                 Gra->G[i][j].Weight = 0;
 42             }
 43             else
 44             {
 45                 Gra->G[i][j].Length = INIFITY;
 46                 Gra->G[i][j].Weight = INIFITY;
 47             }
 48         }
 49     return Gra;
 50 }
 51 
 52 void Insert(Edge E, Graph Gra)
 53 {
 54     Gra->G[E->V1][E->V2].Length = E->Length;
 55     Gra->G[E->V1][E->V2].Weight = E->Weight;
 56 
 57     Gra->G[E->V2][E->V1].Length = E->Length;
 58     Gra->G[E->V2][E->V1].Weight = E->Weight;
 59 }
 60 
 61 Graph CreateGraph(int N,int M)
 62 {
 63     Edge E = (Edge)malloc(sizeof(struct ENode));
 64     Graph Gra = BuildGraph(N);
 65     Gra->Ne = M;
 66     for (int i = 0; i < Gra->Ne; i++)
 67     {
 68         scanf("%d%d%d%d", &(E->V1), &(E->V2), &(E->Length), &(E->Weight));
 69         Insert(E, Gra);
 70     }
 71     return Gra;
 72 }
 73 
 74 int Dist[MAXVERTEXNUM];
 75 int Price[MAXVERTEXNUM];
 76 int Collected[MAXVERTEXNUM];
 77 int FindMin(Graph G)
 78 {
 79     int MinDist= INIFITY;
 80     int Min = -1;
 81     for (int i = 0; i < G->Nv; i++)
 82     {
 83         if (!Collected[i] && Dist[i] < MinDist)
 84         {
 85             MinDist = Dist[i];
 86             Min = i;
 87         }
 88     }
 89     return Min;
 90 }
 91 void Dijkstra(Graph Gra, int V)
 92 {
 93     for (int i = 0; i < Gra->Nv; i++)
 94     {
 95         Dist[i] = Gra->G[V][i].Length;
 96         Price[i] = Gra->G[V][i].Weight;
 97     }
 98     Collected[V] = 1;
 99     while (1)
100     {
101         int Min = FindMin(Gra);
102         if (Min == -1)
103             break;
104         for (int i = 0; i < Gra->Nv; i++)
105         {
106             if (!Collected[i]&&Dist[Min] + Gra->G[Min][i].Length < Dist[i])
107             {
108                 Dist[i] = Dist[Min] + Gra->G[Min][i].Length;
109                 Price[i] = Price[Min] + Gra->G[Min][i].Weight;
110             }
111             else if (!Collected[i]&&Dist[Min] + Gra->G[Min][i].Length == Dist[i] && Price[Min] + Gra->G[Min][i].Weight < Price[i])
112             {
113                 Price[i] = Price[Min] + Gra->G[Min][i].Weight;
114             }
115         }
116         Collected[Min] = 1;
117     }
118 }
119 int main()
120 {
121     int N, M,S,D;
122     scanf("%d%d%d%d", &N, &M, &S, &D);
123     Graph G = CreateGraph(N, M);
124      Dijkstra(G, S);
125     printf("%d %d", Dist[D],Price[D]);
126     return 0;
127 }

View Code