PTA_20_07_图6 _旅游规划

题目描述

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

输入格式

输入说明：输入数据的第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

输出格式

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

3 40

算法分析

本题应该采用Dijkstra算法，应该采用邻接矩阵实现。

本题是在原来的Dijkstra算法进行改进，基本的流程跟原先算法一样

但是新加了一个判断费用的数组，并添加了比较花费金额大小的条件

代码实现

#include<stdio.h>
#include<iostream>

using namespace std;

#define MAXNUM 10
#define INFINITY 65535
struct CNode
{
	int numcity;
	int numhigh;
	int startcity;
	int endcity;
	int distance[MAXNUM][MAXNUM];
	int cost[MAXNUM][MAXNUM];
};
typedef struct CNode* Cgraph;
int c[MAXNUM];//记录花费的数组
int d[MAXNUM];//记录距离的数组

void CreateGraph(Cgraph graph)
{
	int i, j;
	int tmpcity, tmpcity2, roaddist, roadcost;
	cin >> graph->numcity >> graph->numhigh >> graph->startcity >> graph->endcity;
	for (i = 0; i < graph->numcity; i++)
	{
		for (j = 0; j < graph->numcity; j++)
		{
			if (i == j)
			{
				graph->distance[i][j] = 0;
				graph->cost[i][j] = 0;
			}
			else
			{
				graph->distance[i][j] = INFINITY;
				graph->cost[i][j] = INFINITY;
			}
		}
	}
	for (i = 0; i < graph->numhigh; i++)
	{
		cin >> tmpcity >> tmpcity2 >> roaddist >> roadcost;
		graph->distance[tmpcity][tmpcity2] = roaddist;
		graph->distance[tmpcity2][tmpcity] = graph->distance[tmpcity][tmpcity2];
		graph->cost[tmpcity][tmpcity2] = roadcost;
		graph->cost[tmpcity2][tmpcity] = graph->cost[tmpcity][tmpcity2];
	}
	
}


int Shorttravel(Cgraph graph)
{
	int i, j, k, min;
	int final[MAXNUM];
	for (i = 0; i < graph->numcity; i++)
	{
		final[i] = 0;
		(d)[i] = graph->distance[graph->startcity][i];
		(c)[i] = graph->cost[graph->startcity][i];
	}
	(d)[graph->startcity] = 0;
	(c)[graph->startcity] = 0;
	final[graph->startcity] = 1;

	//开始主循环，计算起始点到各点的最短路径
	for (i = 0; i < graph->numcity; i++)
	{
		min = INFINITY;//当前所知离原始点最短的路径
		for (j = 0; j < graph->numcity; j++)
		{
			if (!final[j] && (d)[j] < min)
			{
				k = j;
				min = (d)[j];//j离原始点更近
			}
		}
		final[k] = 1;
		for (j = 0; j < graph->numcity; j++)
		{
			if (!final[j])
			{//注意这里起始点设置的是k,k代表最小点的位置，一下就是对每一个进行遍历
				if (graph->distance[k][j] + (d)[k] < (d)[j])
				{
					(d)[j] = graph->distance[k][j] + (d)[k];
					(c)[j] = (c)[k] + graph->cost[k][j];
				}
				else if (graph->distance[k][j] + (d)[k] == (d)[j] && (c)[j] > (c)[k] + graph->cost[k][j])
				{
					(c)[j] = (c)[k] + graph->cost[k][j];
				}
			}
		}

	}
	return 0;

}




int main()
{
	Cgraph graph;
	graph = (Cgraph)malloc(sizeof(struct CNode));
	CreateGraph(graph);
	Shorttravel(graph);
	int i;
	i = graph->endcity;
	
	cout << d[i] <<" " << c[i];
}