有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。
输入格式: 输入说明:输入数据的第1行给出4个正整数N、M、S、D,其中N(2≤N≤500)是城市的个数,顺便假设城市的编号为0~(N?1);M是高速公路的条数;S是出发地的城市编号;D是目的地的城市编号。随后的M行中,每行给出一条高速公路的信息,分别是:城市1、城市2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过500。输入保证解的存在。
输出格式: 【PTA 浙大《数据结构(第二版)》 07-图6 旅游规划】在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。
输入样例:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出样例:
3 40
思路 迪杰斯特拉算法,其中定义边的时候需要代表距离和收费的两个权重,定义图时两个邻接矩阵(一个也行 不想改了)
编译器 C(gcc)
#include
#include
#define true 1
#define false 0 定义bool值
#define INFINITY 65535
#define ERROR -1
typedef int Vertex;
typedef int DataType;
typedef struct GNode *PtrToGNode;
//typedef int Cost;
typedef int WeightType;
/*定义图*/
struct GNode
{
int Nv;
int Ne;
WeightType G[500][500];
WeightType C[500][500];
};
typedef PtrToGNode MGraph;
/*定义边*/
typedef struct ENode *PtrToENode;
struct ENode
{
Vertex V1,V2;
WeightType Weight;
WeightType Cost;
};
typedef PtrToENode Edge;
MGraph CreatGraph(int VertexNum)
{
Vertex V,W;
MGraph Graph;
Graph=(MGraph)malloc(sizeof(struct GNode));
Graph->Nv=VertexNum;
Graph->Ne=0;
for(V=0;
VNv;
V++)
{
for(W=0;
WNv;
W++)
{
Graph->G[V][W]=INFINITY;
Graph->C[V][W]=INFINITY;
}
}
return Graph;
}
void InsertEdge(MGraph Graph,Edge E)
{
Graph->G[E->V1][E->V2]=E->Weight;
Graph->G[E->V2][E->V1]=E->Weight;
Graph->C[E->V1][E->V2]=E->Cost;
Graph->C[E->V2][E->V1]=E->Cost;
}
Vertex FindMinDist(MGraph Graph,int dist[],int collected[])
{
Vertex MinV,V;
int MinDist=INFINITY;
for(V=0;
VNv;
V++)
{
if(collected[V]==false&&dist[V]Nv;
V++)
{
dist[V]=Graph->G[S][V];
cost[V]=Graph->C[S][V];
if(dist[V]Nv;
W++)
{
if(collected[W]==false&&Graph->G[V][W]G[V][W]G[V][W];
path[W]=V;
cost[W]=cost[V]+Graph->C[V][W];
}
else if((dist[V]+Graph->G[V][W]==dist[W])&&cost[V]+Graph->C[V][W]C[V][W];
}
}} }
printf("%d %d",dist[D],cost[D]);
}int main()
{
MGraph Graph;
Edge E;
//Cost C;
int Nv,i;
int S,D;
int dist[500],path[500],cost[500];
scanf("%d",&Nv);
//Nv++;
Graph=CreatGraph(Nv);
scanf("%d",&(Graph->Ne));
scanf("%d",&S);
scanf("%d",&D);
if(Graph->Ne!=0)
{
E=(Edge)malloc(sizeof(struct ENode));
//C=(Cost)malloc(sizeof(struct CNode));
for(i=0;
iNe;
i++)
{
scanf("%d %d %d %d",&E->V1,&E->V2,&E->Weight,&E->Cost);
InsertEdge(Graph,E);
} }
Dijkstra(Graph,dist,path,cost,S,D);
system("pause");
return 0;
}
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧(用class类实现链表)
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶(线性表)
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程(多态、抽象类、接口)- Java - 细节狂魔