1003 Emergency (Dijkstra)

标签: OJ题目  # PAT甲级

题目描述

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

输入格式

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1 and c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

输出格式

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

输入样例

5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

输出样例

2 4

题目大意

无向图中,给出每个点的点权,每个边的边权(即两点之间距离),要使起点到终点距离最短,求最短路径数,并求出最大点权之和。

思路

单源最短路径问题。采用Dijkstra算法,该算法的思想为,设置数组d,代表源点与各顶点的最短距离。经过n(点数)次遍历,每次遍历找到当前与源点s距离最短的顶点u,并以该顶点u为中介点,找到其经过并未访问的结点v,判断其能否使d[v]更优(即length[s->u]+d[u]<d[v])。本题目新增点权wm、最短路径数目num两个量,和d的处理方法类似。即:

  • length[s->u]+d[u]<d[v]时,num[v]更新为num[u],wm[v]更新为wm[u]+w[v]。
  • length[s->u]+d[u]=d[v]时,num[v]更新为num[u] + num[v]。而只有wm[u]+w[v]>wm[v]时(以u为中介使wm更优),才更新wm[v]。

该题一开始没通过,因为我忘了这是个无向图,输入数据时需要考虑到。

AC代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct node{
	int v, dis; //目标顶点和边权 
};
const int maxv = 510, INF = 1000000000;
vector<node> Adj[maxv];
int d[maxv]; //源点到各顶点最短路径长度
int num[maxv]; //最短路径条数
int wm[maxv]; //最多救援队数
int w[maxv]; //各点救援队数 
bool vis[maxv] = {false}; 
int n, m; //城市数 路径数 
int s, e; //起点和终点

void Dijkstra(int s){
	fill(d, d + maxv, INF);
	fill(num, num + maxv, 0);
	fill(wm, wm + maxv, 0);
	d[s] = 0;
	num[s] = 1;
	wm[s] = w[s];
	for(int i = 0; i < n; i++){
		int u = -1, min = INF;
		for(int j = 0; j < n; j++){ //找到最小d[u] 
			if(vis[j] == false && d[j] < min){
				u = j;
				min = d[u];
			} 
		}
		if(u == -1) return;
		vis[u] = true;
		for(int j = 0; j < Adj[u].size(); j++){
			int v = Adj[u][j].v; //u能到达的顶点
			if(vis[v] == false){
				if(d[v] > d[u] + Adj[u][j].dis){
					//以u为中介点使d[v]更优 
					d[v] = d[u] + Adj[u][j].dis;
					num[v] = num[u];
					wm[v] = wm[u] + w[v];
				}
				else if(d[v] == d[u] + Adj[u][j].dis){
					num[v] += num[u];
					if(wm[v] < wm[u] + w[v])
						wm[v] = wm[u] + w[v];
				}
			}
		}
	}
}

int main(){
	cin>>n>>m>>s>>e;
	for(int i = 0; i < n; i++)
		cin>>w[i];
	int c1, c2, l;
	node tmp;
	for(int i = 0; i < m; i++){
		cin>>c1>>c2>>l;
		tmp.v = c2;
		tmp.dis = l;
		Adj[c1].push_back(tmp);
		tmp.v = c1;
		Adj[c2].push_back(tmp);
	}
	Dijkstra(s);
	cout<<num[e]<<" "<<wm[e]; 
	return 0;
}

在这里插入图片描述

版权声明:本文为qq_43072010原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43072010/article/details/104793548

智能推荐

Hibernate学习总结(一)

一、Hibernate简介 一个持久层的ORM框架。ORM:Object Relational Mapping(对象关系映射)。指的是将一个Java中的对象与关系型数据库中的表建立一种映射关系,从而操作对象就可以操作数据库中的表。 二、Hibernate入门 1、创建一个项目,引入jar包 hibernate用到的jar包 2、创建表 3、创建实体类 4、创建映射(*****) 映射需要通过XML...

Linux系统NFS

文章目录 1. nfs简介 1.1 nfs特点 1.2 使用nfs的好处 1.3 nfs的体系组成 1.4 nfs的应用场景 2. nfs工作机制 2.1 RPC 2.2 NIS 2.3 nfs工作机制 3. exports文件的格式 4. nfs管理 5. 作业 5.1手动搭建一个nfs服务器 5.1.1开放/nfs/shared目录,供所有用户查阅资料 5.1.2 开放/nfs/upload目...

关于java中String,StringBuffer,StringBuilder的区别以及StringBuffer,StringBuilder的安全性问题

这里的结果就是正确的然后我们来看他的append方法 它在前边加了一个synchronized来修饰,相当于同时只能有一个线程来访问他,这样就不会产生上边的问题但同时他的效率也就比StringBuilder低,...

Django连接现有mysql数据库

1、打开cmd后cd到项目位置 2、建立项目 django-admin startproject test2 3、编辑项目中的配置文件, mysite/settings.py ,告诉Django你的数据库连接参数和数据库名。具体的说,要提供 DATABASE_NAME , DATABASE_ENGINE , DATAB...

ShareSDK新浪微博登录时报错error:redirect_uri_mismatch

今天用 ShareSDK 做第三方登录的时候碰到个问题,明明在微博平台的应用审核已经通过了,但是调用登录接口的时候一直报错,错误如下: 出现这个错误是因为在微博开放平台上没有设置回调地址,或者设置的回调地址与本地XML中的地址不一致。 在sharesdk.xml文件当中对于微博的设置: 其中RedirectUrl为设置的回调地址,这里的地址必须要与微博开发平台设置的地址相同,否则就会出现上面的错误...

猜你喜欢

python解析网络封包方法

2019独角兽企业重金招聘Python工程师标准>>> 在使用Python解析网络数据包时,使用网络字节序解析,参见下表。 C语言的数据类型和Python的数据类型对照表请参见下表。 接下来对封包与解包进行举例说明。 version type id content unsigned short unsigned short unsigned int unsigned int 封包...

python3:时间方法,异常处理,系统文件相关模块(os)

文章目录 时间方法 time模块 时间表示方法: time模块的方法 datetime模块 异常处理 触发异常 创建mydiv.py脚本,要求如下: 创建myerror.py脚本,要求如下: os模块 实现ls -R(os.walk) os.path pickle模块 记账脚本 时间方法 time模块 时间表示方法: 时间戳:自1970-1-1 0:00:00到某一时间点之间的秒数 UTC时间:世...

负载均衡群集——LVS+DR模型

一、实验组成 调度器 192.168.100:41 web1 192.168.100:42 web2 192.168.100.43 NFS共享服务器 192.168.100.44 二、实验拓扑 三、实验配置 3.1在调度器配置:192.168.100.41 配置虚拟IP地址(VIP) 调整/proc响应参数 对于 DR 群集模式来说,由于 LVS 负载调度器和各节点需要共用 VIP 地址,应该关闭...

adb无线连接时appium找不到设备

问题描述 以前使用USB连接真机,运行appium时一直正常,连接参数如下: 最近为了方便,使用adb无线连接真机,adb版本为1.0.40,真机安卓版本10,连接后,通过adb devices能够查看到连接的设备: adb无线连接是正常的,但每次运行时appium都找不到无线连接的设备,陷入重启adb循环: 解决流程 1.因为是没找到设备,所以在appium连接参数中增加了"udid&...

Mybatis_CRUD(基于xml的增删改查操作)

dao IUserDao domain User QueryVo SqlMapConfig.xml com.itheima.dao IUserDao.xml com.itheima.test 执行原理图:...