PTA 7

发布时间：2024-12-16 12:02

案例7: 案例7: 通过团队协作提高谈判效果 #生活技巧# #谈判技巧# #商业谈判案例#

题目描述

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

输入格式:

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

输出格式:

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

输入样例:

4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20 123456

输出样例:

3 40 1

思路分析

我是申请了两个图的空间，图G的权存储两个点之间的距离，图M的权存储两个点之间的过路费。定义一个初始化函数，把图G和M里面二维数组里面的值最大化，再定义一个代表i距离起点的距离的数组dist，代表i距离起点花费过路费的数组cost和bool数组代表是否访问过的visit。定义一个Dijkstra函数，把起点的visit变为true，代表访问过，然后找到距离起点最近切没有被访问过的城市，然后循环找到最短路径，如果最短路径相同，过路费不同，过路费更新为少的那个。这样最后dist数组里面就是起点到其他每个点的最短距离，cost数组里面存储的就是在最短距离的基础上，花费的最少过路费。只需要输出目的地的dist和cost即可。

源代码

#include <stdio.h> #include<stdlib.h> #include <stdbool.h> #define INFINITY 0x3f3f3f3f #define MaxVertexNum 510 /* maximum number of vertices */ typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */ typedef int WeightType; typedef struct GNode *PtrToGNode; struct GNode{ int Nv; int Ne; WeightType G[MaxVertexNum][MaxVertexNum]; }; typedef PtrToGNode MGraph; int sta,end; int dist[MaxVertexNum],cost[MaxVertexNum]; bool visit[MaxVertexNum]={false}; MGraph M; MGraph ReadG() { MGraph G=(MGraph)malloc(sizeof(struct GNode)); M=(MGraph)malloc(sizeof(struct GNode)); scanf("%d%d%d%d",&G->Nv,&G->Ne,&sta,&end); int i,j; for(i=0;i<G->Nv;i++) { for(j=0;j<G->Nv;j++) { G->G[i][j]=INFINITY; M->G[i][j]=INFINITY; if(i==j){ G->G[i][j]=0; M->G[i][j]=0; } } } for(i=0;i<G->Ne;i++) { int a,b,x,y; scanf("%d%d%d%d",&a,&b,&x,&y); G->G[a][b]=x; G->G[b][a]=x; M->G[a][b]=y; M->G[b][a]=y; } for (i = 0; i < G->Nv; i++) { dist[i]=G->G[sta][i]; cost[i]=M->G[sta][i]; } dist[G->Nv]=INFINITY; return G; } void dijkstra(MGraph G) { visit[sta] = true;//先将起始点加入集合 int minpoint;//此变量为将记入集合的点 for(int i1 = 0; i1 < G->Nv; i1++) { minpoint = G->Nv;//编号M城市并不存在，st到M的距离也为INF(已在主函数中设置) for(int i = 0; i < G->Nv; i++)//此循环寻找距离st且不再集合中的最短距离点 { if((!visit[i]) && (dist[i] < dist[minpoint]))// minpoint = i; } if(minpoint == G->Nv ) break;//未找到，此时结束循环 visit[minpoint] = true;//将找到的点加入集合 for(int i = 0; i < G->Nv;i++)//此循环用于更新st通过集合个点所能连接到的点的最短路径 { if(!visit[i] && (dist[i] > dist[minpoint] + G->G[minpoint][i])) { dist[i] = dist[minpoint] + G->G[minpoint][i]; cost[i] = M->G[minpoint][i] + cost[minpoint]; } else if(!visit[i] && (dist[i] == dist[minpoint] +G->G[minpoint][i])//长度相同费用更少的更新为费用少的 && (cost[i] > cost[minpoint] + M->G[minpoint][i])) { cost[i] = (cost[minpoint] + M->G[minpoint][i]); } } } } int main() { MGraph G=ReadG(); dijkstra(G); printf("%d %d",dist[end],cost[end]); return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495'