L2-001 紧急救援(迪杰斯特拉应用)

2024-04-23 20:58

本文主要是介绍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

这个题目很热闹啊,又是最短路,最短路经过最短条数,又是每个城市都有一个权值,从起点到终点的权值最大,还要输出路径(心想这都是啥?我只会求最短路的长度,还是自己太菜了,没有对迪杰斯特拉有很透彻的理解,还是自己太菜)。所以写个博客补充一下知识。

这个题目是从起点最快(最短路)到达终点,但是还有另一个要求,经过节点的权值和要尽量大,还要输出路径。

普通的最短路就是套模板。这个输出路径就是用一个数组来找这个点的前驱节点,然后在输出路径的时候,就像链表式的,往前找前驱节点,就是下面这样 path[ ]数组是一个点的前驱节点,然后存到vector 中,倒序输出,就得到路径。  

void print()
{int i;vector<int>mp;for(i=e;i!=s;i=path[i])mp.push_back(i);	mp.push_back(i);reverse(mp.begin(),mp.end());for(int i=0;i<mp.size();i++){if(i)cout<<' ';cout<<mp[i];}	
}

当然还有DFS回溯输出路径(我好菜,递归也没有学的很精),先递到起点,然后再往回回溯输点,这种思想要记住,对于一些输出前驱路径的要求DFS递归输出就可以了,下面代码:
 

 
//dfs回溯输出  
//X一开始传进终点 
void dfs(int x)
{if(x==s)printf("%d",x);else{dfs(path[x]);printf(" %d",x);}	
}

然后看这个最短路径经过路的条数,这个我也不是很懂(菜死了我,只会套板子),我们需要新开一个数组就是由原点到各个点的路径长度,就是过了几条边。迪杰斯特拉基本的东西就是由原点开始找到那个权值最小的那个临近点,将它放进最短路答案的集合中,再由这个点出发到其他的点,看看由原点到这个点,还是由这个新的出发点到这个点近,近的话,更新数据,近的话(以下这个操作我不是很明白,听大神说是 优化用的,不知道怎么搞的),就是近的话,由原点到这个点的路径边数变为上一个点(上一个点作为出发点找他周围的点;就是上一个点过来的到这个点了)路径边数  (举个例子0->1 长度是1,现在1->2 数据要更新,权值更新为d[pos]+map[pos][j] (注意),由原点到这个2点路径长度变为 1(注意),然后在下一次循环时候,这个条件!vis[j]&&d[j]>d[pos]+map[pos][j] 就不会满足(注意),去else if 那个条件进去,由原点到这个点的路径长度这时 1+1=2 更新了,不知道搞这样子是为啥,可能有更高级的用处,我辣鸡 不是很懂为啥这样做)。就是下面这个操作。好玄。   

for(int i=0;i<n;i++)   //这个不影响  {minv=inf;for(int j=0;j<n;j++){if(!vis[j]&&minv>d[j]){minv=d[j];pos=j;}}vis[pos]=1;for(int j=0;j<n;j++){if(!vis[j]&&d[j]>d[pos]+map[pos][j]){d[j]=map[pos][j]+d[pos];pathsum[j]=pathsum[pos];      valsum[j]=valsum[pos]+val[j];path[j]=pos;}else if(!vis[j]&&d[j]==d[pos]+map[pos][j]){pathsum[j]+=pathsum[pos];  if(valsum[j]<valsum[pos]+val[j]){valsum[j]=valsum[pos]+val[j];path[j]=pos;}}}}

 还有一个需求,(在每个点上都会有一个权值,经过时会加上),求出在最短路的基础上看看怎么使得这个权值最大。我们现在再来一个数组来存储由原点到各个点的权值,一开始初始条件就是每个城市每个点都是 原先的权值。就是上面的代码。这个还是比较好想的。

代码:

 

#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<string.h>
const int maxn=1005;
typedef long long ll;
using namespace std;
const int inf=1e8;int map[maxn][maxn];
int d[maxn];           //到每个点经过路的权值  
int vis[maxn];int val[maxn];       //每个点初始的权值 
int valsum[maxn];   //由起点到每个点的权值  
int path[maxn];			//这个点之前的点 
int pathsum[maxn];      //到每个点的经过路的条数 int n,m,s,e;void init()
{memset(vis,0,sizeof(vis));memset(path,0,sizeof(path));memset(pathsum,0,sizeof(pathsum));for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(i==j)map[i][j]=0;elsemap[i][j]=inf;valsum[i]=val[i];}	
} void jd()
{for(int i=0;i<n;i++){d[i]=map[s][i];}pathsum[s]=1;d[s]=0;int minv=inf;int pos;for(int i=0;i<n;i++){minv=inf;for(int j=0;j<n;j++){if(!vis[j]&&minv>d[j]){minv=d[j];pos=j;}}vis[pos]=1;for(int j=0;j<n;j++){if(!vis[j]&&d[j]>d[pos]+map[pos][j]){d[j]=map[pos][j]+d[pos];pathsum[j]=pathsum[pos];valsum[j]=valsum[pos]+val[j];path[j]=pos;}else if(!vis[j]&&d[j]==d[pos]+map[pos][j]){pathsum[j]+=pathsum[pos];if(valsum[j]<valsum[pos]+val[j]){valsum[j]=valsum[pos]+val[j];path[j]=pos;}}}}
}void print()
{int i;vector<int>mp;for(i=e;i!=s;i=path[i])mp.push_back(i);	mp.push_back(i);reverse(mp.begin(),mp.end());for(int i=0;i<mp.size();i++){if(i)cout<<' ';cout<<mp[i];}	
}int main()
{cin>>n>>m>>s>>e;for(int i=0;i<n;i++)scanf("%d",&val[i]);init();int x,y,z;for(int i=0;i<m;i++){scanf("%d%d%d",&x,&y,&z);map[x][y]=map[y][x]=z;}jd();printf("%d %d\n",pathsum[e],valsum[e]);print();return 0;
}

(路还很长)。

 

这篇关于L2-001 紧急救援(迪杰斯特拉应用)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/929872

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

python中time模块的常用方法及应用详解

《python中time模块的常用方法及应用详解》在Python开发中,时间处理是绕不开的刚需场景,从性能计时到定时任务,从日志记录到数据同步,时间模块始终是开发者最得力的工具之一,本文将通过真实案例... 目录一、时间基石:time.time()典型场景:程序性能分析进阶技巧:结合上下文管理器实现自动计时

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

Spring AI集成DeepSeek三步搞定Java智能应用的详细过程

《SpringAI集成DeepSeek三步搞定Java智能应用的详细过程》本文介绍了如何使用SpringAI集成DeepSeek,一个国内顶尖的多模态大模型,SpringAI提供了一套统一的接口,简... 目录DeepSeek 介绍Spring AI 是什么?Spring AI 的主要功能包括1、环境准备2

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav