PTA 07-图6 旅游规划 (25分)

题目地址 https://pta.patest.cn/pta/test/15/exam/4/question/717

5-9 旅游规划 (25分)

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

输入格式:

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

输出格式:

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

输入样例:

输出样例:

3 40

/*

评测结果

时间	结果	得分	题目	编译器	用时（ms）	内存（MB）	用户

2017-07-04 21:04	正在评测	0	5-9	gcc	无	无

测试点结果

测试点	结果	得分/满分	用时（ms）	内存（MB）

测试点1	答案正确	12/12	3	3

测试点2	答案正确	5/5	3	3

测试点3	答案正确	4/4	4	3

测试点4	答案正确	4/4	69	3

25分的题，套一下dijkstra就AC了

*/

#include<stdio.h>

#define MAXN 500

#define TRUE 1

#define FALSE 0

#define INFINITY 100000

#define ERROR -1

struct Edge

{

	int dist;

	int cost;

} gMatrix[MAXN][MAXN];

struct Vertex

{

	int collected;

	int totalDist;

	int totalCost;

} gNodeTable[MAXN];

void InitMatrixAndTable()

{

	int i,j;

	for(i=0;i<MAXN;i++)

	{

		for(j=0;j<MAXN;j++)

		{

			gMatrix[i][j].dist=INFINITY;

			gMatrix[i][j].cost=0;

		}

		gNodeTable[i].collected=FALSE;

		gNodeTable[i].totalCost=INFINITY;

		gNodeTable[i].totalDist=INFINITY;

	}

}

int FindNextVertex(int N)

{

	int minIDX=ERROR;

	int minDist=INFINITY;

	int i;

	for(i=0;i<N;i++)

	{

		if(gNodeTable[i].collected==FALSE)

		{

			if(minDist>gNodeTable[i].totalDist)

			{

				minIDX=i;

				minDist=gNodeTable[i].totalDist;

			}

		}

	}

	return minIDX;

}

void Dijkstra(int N,int S)

{

	int i,j,vertex;

	vertex=S;

	gNodeTable[vertex].totalDist=0;

	gNodeTable[vertex].totalCost=0;

	while(vertex != ERROR)

	{

		gNodeTable[vertex].collected=TRUE;

		for(i=0;i<N;i++)

		{

			if(gMatrix[vertex][i].dist==INFINITY)

				continue;

			if(gNodeTable[i].totalDist>gNodeTable[vertex].totalDist+gMatrix[vertex][i].dist)

			{

				gNodeTable[i].totalDist=gNodeTable[vertex].totalDist+gMatrix[vertex][i].dist;

				gNodeTable[i].totalCost=gNodeTable[vertex].totalCost+gMatrix[vertex][i].cost;

			}

			if(gNodeTable[i].totalDist==gNodeTable[vertex].totalDist+gMatrix[vertex][i].dist)

			{

				if(gNodeTable[vertex].totalCost + gMatrix[vertex][i].cost < gNodeTable[i].totalCost)

				{

					gNodeTable[i].totalDist=gNodeTable[vertex].totalDist+gMatrix[vertex][i].dist;

					gNodeTable[i].totalCost=gNodeTable[vertex].totalCost+gMatrix[vertex][i].cost;

				}

			}

		}

		vertex=FindNextVertex(N);

	}

}

int main()

{

	int i,v1,v2,dist,cost;

	int N,M,S,D; //N节点数 M边数 S起点 D终点

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

	InitMatrixAndTable();

	for(i=0;i<M;i++)

	{

		scanf("%d %d %d %d",&v1,&v2,&dist,&cost);

		gMatrix[v1][v2].dist=dist;

		gMatrix[v1][v2].cost=cost;

		gMatrix[v2][v1].dist=dist;

		gMatrix[v2][v1].cost=cost;

	}

	Dijkstra(N,S);

	printf("%d %d",gNodeTable[D].totalDist,gNodeTable[D].totalCost);

}

巴特西

PTA 07-图6 旅游规划 (25分)

输入格式:

输出格式:

输入样例:

输出样例:

最新文章

热门文章