频道澳门葡京手机版网址
登录注册
澳门葡京手机版网址 > 澳门葡京手机版网址 > App开发 > 其他 > 正文
PAT L2-001题目解答
2017-03-24 09:09:00           
收藏   我要投稿

PAT L2-001题目解答:作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。

每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候,你的任务是带领你的救援队尽快赶往事发地,同时,一路上召集尽可能多的救援队。

输入格式:

输入第一行给出4个正整数N、M、S、D,其中N(2<=N<=500)是城市的个数,顺便假设城市的编号为0~(N-1);M是快速道路的条数;S是出发地的城市编号;D是目的地的城市编号。第二行给出N个正整数,其中第i个数是第i个城市的救援队的数目,数字间以空格分隔。随后的M行中,每行给出一条快速道路的信息,分别是:城市1、城市2、快速道路的长度,中间用空格分开,数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:

第一行输出不同的最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔,输出首尾不能有多余空格。

输入样例:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2
输出样例:
2 60
0 1 3

迪杰斯特拉算法的变种,在计算最短路径的同时将两个点的救援队数量相加,碰到两个路径相等的时候,就比较救援队数量的多少,谁多选谁。

#include
#include
using namespace std;
const int INF = 100000;
const int MAX = 505;
bool visited[MAX];int dis[MAX];int prepath[MAX];int car[MAX];int totcar[MAX];int pathnum[MAX];//是否已最小,最短路径存放数组,前驱结点数组,救援队数量,路径多少数组
int edge[MAX][MAX];
void estab(int n, int m)//用于初始化
{
	int start, over, len;
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++)
			edge[i][j] = INF;
	for (int q = 0;q < m;q++)
	{
		cin >> start >> over >> len;
		edge[start][over]=edge[over][start] = len;
	}
}
void dijkstra(int v0, int n)//最短路径算法
{
	dis[v0] = 0;
	visited[v0] = true;
	int begin = v0;
	totcar[v0] = car[v0];
	pathnum[v0] = 1;
	int min;
	for (int i = 0;i < n;i++)
	{
		dis[i] = edge[v0][i];
		if ((dis[i] != INF)&&(i != v0))
		{
			prepath[i] = v0;
			totcar[i] = car[v0] + car[i];
			pathnum[i] = 1;
		}
	}
	for (int q = 1;q < n;q++)
	{
		min = INF;
		for (int m = 0;m < n;m++)
		{
			if ((!visited[m]) && (dis[m] < min))
			{
				begin = m;
				min = dis[m];
			}
		}
		visited[begin] = true;
		for (int i = 0;i < n;i++)
		{
			if (!visited[i])
			{
				if ((dis[begin] + edge[begin][i]) < dis[i])
				{
					prepath[i] = begin;
					totcar[i] = totcar[begin]+car[i];
					pathnum[i] = pathnum[begin];
					dis[i] = dis[begin] + edge[begin][i];
					totcar[i] = totcar[begin] + car[i];
				}
				else if ((dis[begin] + edge[begin][i]) == dis[i])//如果相等比较救援队数量
				{
					pathnum[i]+= pathnum[begin];
					if (totcar[i] < (totcar[begin] + car[i]))
					{
						prepath[i] = begin;
						totcar[i] = totcar[begin] + car[i];
					}
				}
			}
		}
	}
	
}
int main()
{
	int m, n, s, d;
	cin >> n>>m>>s>>d;
	int current = d;
	for (int i = 0;i < n;i++)
		cin >> car[i];
	int count = 0;
	int path[MAX];
	fill(visited, visited + MAX,0);
	estab(n, m);
	dijkstra(s, n);
	while (current != s)
	{
		path[count++] = current;
		current = prepath[current];
	}
	path[count] = s;
	cout << pathnum[d] << " " << totcar[d]<
点击复制链接 与好友分享!回澳门葡京手机版网址澳门葡京手机版网址
上一篇:python模型过拟合
下一篇:用eclipse远程调试Java程序
相关文章
图文推荐
点击排行

关于大家 | 联系大家 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 澳门葡京手机版网址_澳门新莆京娱乐_www.88807.com - 点此进入--致力于做实用的IT技术学习网站

XML 地图 | Sitemap 地图