PAT 1163 Dijkstra Sequence
个人学习记录,代码难免不尽人意。
Dijkstra’s algorithm is one of the very famous greedy algorithms.
It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to all the other vertices of the given graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
In this algorithm, a set contains vertices included in shortest path tree is maintained. During each step, we find one vertex which is not yet included and has a minimum distance from the source, and collect it into the set. Hence step by step an ordered sequence of vertices, let’s call it Dijkstra sequence, is generated by Dijkstra’s algorithm.
On the other hand, for a given graph, there could be more than one Dijkstra sequence. For example, both { 5, 1, 3, 4, 2 } and { 5, 3, 1, 2, 4 } are Dijkstra sequences for the graph, where 5 is the source. Your job is to check whether a given sequence is Dijkstra sequence or not.
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers N v(≤10 3 ) and N e (≤10 5 ), which are the total numbers of vertices and edges, respectively. Hence the vertices are numbered from 1 to Nv .Then N elines follow, each describes an edge by giving the indices of the vertices at the two ends, followed by a positive integer weight (≤100) of the edge. It is guaranteed that the given graph is connected.
Finally the number of queries, K, is given as a positive integer no larger than 100, followed by K lines of sequences, each contains a permutationof the N v vertices. It is assumed that the first vertex is the source for each sequence.
All the inputs in a line are separated by a space.
Output Specification:
For each of the K sequences, print in a line Yes if it is a Dijkstra sequence, or No if not.
Sample Input:
5 7
1 2 2
1 5 1
2 3 1
2 4 1
2 5 2
3 5 1
3 4 1
4
5 1 3 4 2
5 3 1 2 4
2 3 4 5 1
3 2 1 5 4
Sample Output:
Yes
Yes
Yes
No
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
using namespace std;
const int maxn=1010;
const int INF=1000000000;
int G[maxn][maxn];
int d[maxn];
bool visit[maxn];
bool dijkstra(int list[],int n){fill(d,d+maxn,INF);fill(visit,visit+maxn,false);d[list[0]]=0;int count=0;for(int i=0;i<n;i++){int m=-1,min=INF;for(int j=1;j<=n;j++){if(d[j]<min&&!visit[j]){m=j;min=d[j];}}if(d[m]!=d[list[count]]){return false;}else count++;visit[m]=true;for(int j=1;j<=n;j++){if(!visit[j]&&G[m][j]!=INF&&d[j]>d[m]+G[m][j]){d[j]=d[m]+G[m][j];}}}return true;
}int main(){for(int i=0;i<maxn;i++){for(int j=0;j<maxn;j++){G[i][j]=INF;}}int n,m;scanf("%d %d",&n,&m);for(int i=0;i<m;i++){int a,b,dis;scanf("%d %d %d",&a,&b,&dis);G[a][b]=dis;G[b][a]=dis;}int k;scanf("%d",&k);for(int i=0;i<k;i++){int list[n];for(int j=0;j<n;j++){scanf("%d",&list[j]);}if(dijkstra(list,n)){printf("Yes\n");}else{printf("No\n");}}
}
这道题我一开始的做法是先正常用dijkstra算法求出d数组,然后再用给的序列求出另外一个d数组比较两个数组是否一致,如果一致输出yes,不一样输出no。**但是测试点1,3报错!证明不能这样做。后来我想了很久终于想明白了,哪怕是不按照dijkstra序列顺序,最终得到的结果也有可能相同!**这道题最简单的做法还是在dijkstra算法中判断当前处理节点和序列对应节点的距离源点的距离是否一致,如果不一致的话就可以判断不是dijkstra序列!因为可以肯定不是最小距离,一定不会在这个位置出现!
这道题让我知道,如果做题的时候部分正确,自己又肯定算法本身没有问题,肯定是出发点搞错了!可以换个方向重新写!
相关文章:
PAT 1163 Dijkstra Sequence
个人学习记录,代码难免不尽人意。 Dijkstra’s algorithm is one of the very famous greedy algorithms. It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to all the other v…...

嵌入式学习之进程
1.进程间通信概述 UNIX系统IPC是各种进程通信方式的统称。 2.管道通信原理 特点: 1.它是半双工的(即数据只能在一个方向上流动),具有固定的读端和写端。 2.它只能用于具有亲缘关系的进程之间通信(也是父子进程或者…...

C#-单例模式
文章目录 单例模式的概述为什么会有单例模式如何创建单例模式1、首先要保证,该对象 有且仅有一个2、其次,需要让外部能够获取到这个对象 示例通过 属性 获取单例 单例模式的概述 总结来说: 单例 就是只有 一个实例对象。 模式 说的是设计模式…...
WSNs 安全技术
WSNs 多用于军事,特殊现场的警戒保护、商业区域的安防,作为任务型网 络,不仅要进行数据传输,而且要进行数据采集和融合,任务的协同控制等,如何 保证任务执行的机密性,数据产生的可靠性数据融合…...
H5如何做页面下拉刷新和上拉加载
这里以vant为例 结构 <van-pull-refreshv-model"isLoading"success-text"刷新成功"refresh"onRefresh"><van-liststyle"height:100%"v-model"loading":finished"finished"finished-text"没有更多了…...
Camunda 7.x 系列【42】事件子流程
有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot 版本 2.7.9 本系列Camunda 版本 7.19.0 源码地址:https://gitee.com/pearl-organization/camunda-study-demo 文章目录 1. 概述2. 案例演示2.1 流程模型2.2 测试1. 概述 事件子流程是由事件触发的子流程,可存在…...

JVM类的加载过程
加载过程 JVM的类的加载过程分为五个阶段:加载、验证、准备、解析、初始化。 加载 加载阶段就是将编译好的的class文件通过字节流的方式从硬盘或者通过网络加载到JVM虚拟机当中来。(我们平时在Idea中书写的代码就是放在磁盘中的,也可以通…...

Jmeter如何设置中文版
第一步:找到 apache-jmeter-5.4.3\bin目录下的 jmeter.properties 第二步:打开 三,ctrf 输入languageen,注释掉,增加以行修改如下 四,ctrs 保存修改内容,重新打开jmeter就可以了...

flutter自定义按钮-文本按钮
目录 前言 需求 实现 前言 最近闲着无聊学习了flutter的一下知识,发现flutter和安卓之间,页面开发的方式还是有较大的差异的,众所周知,android的页面开发都是写在xml文件中的,而flutter直接写在代码里(da…...

无涯教程-Android - CheckBox函数
CheckBox是可以由用户切换的on/off开关。为用户提供一组互不排斥的可选选项时,应使用复选框。 CheckBox 复选框属性 以下是与CheckBox控件相关的重要属性。您可以查看Android官方文档以获取属性的完整列表以及可以在运行时更改这些属性的相关方法。 继承自 android.widget.T…...
[Go版]算法通关村第十五关青铜——用4KB内存寻找重复元素
目录 题目:用4KB内存寻找重复元素思路分析:使用位存储如何存储这32000个整数?每个整数对应在位图中的存储状态举例如何判断是重复的?具体的步骤 复杂度:时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)Go…...

OJ练习第159题——消灭怪物的最大数量
消灭怪物的最大数量 力扣链接:1921. 消灭怪物的最大数量 题目描述 你正在玩一款电子游戏,在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ,其中 dist[i] 是第 i 个怪物与城市的 初始距离&#…...
Prometheus-Rules(规则)
文章目录 一、介绍二、配置 Prometheus 使用规则文件三、 规则文件语法规则文件语法全局Recording rules(记录规则)2 Alerting rules(警报规则)3 模板化如何使用四、检查规则文件语法五、发送警报通知一、介绍 Prometheus规则是一种逻辑表达式,可用于定义有关监控数据的逻…...

打卡智能中国(六):村里出了“飞行员”
提起返乡青年,你的第一印象是什么?失败、躺平、卷不动了? 我们在浙江、福建、青海等地,参观一些农业智能化项目时,陪同参观的“飞手”,高兴地跟我们分享自己的心路历程: 在家门口做农业无人机操…...

自动化运维工具Ansible之playbooks剧本
自动化运维工具Ansible之playbooks剧本 一、playbooks1.playbooks简述2.playbooks剧本格式3.playbooks组成部分 二、实例1.编写脚本2.运行playbook3.定义、引用变量4.指定远程主机sudo切换用户5.when条件判断6.迭代7.Templates 模块8.tags 模块9.Roles 模块 三、编写应用模块1.…...

K8S访问控制------认证(authentication )、授权(authorization )、准入控制(admission control )体系
一、账号分类 在K8S体系中有两种账号类型:User accounts(用户账号),即针对human user的;Service accounts(服务账号),即针对pod的。这两种账号都可以访问 API server,都需要经历认证、授权、准入控制等步骤,相关逻辑图如下所示: 二、authentication (认证) 在…...

开开心心带你学习MySQL数据库之第三篇上
学校的项目组有必要加入吗? 看你的初心. ~~如果初心是通过这个经历能够提高自己的技术水平 ~~是可以考虑的 ~~如果初心是通过这个经历提高自己找工作的概率 ~~这个是不靠谱的,啥用没有 ~~如果初心是通过这个体验更美好的大学生活 ~~靠谱的 秋招,应届生,找工作是非常容易的!!! …...

Mysql批量插入大量数据的方法
使用存储过程进行插入, 在navicate中示例如下: 输入需要的参数点击完成 在begin end中输入代码,示例代码如下 CREATE DEFINERskip-grants userskip-grants host PROCEDURE batch_insert() BEGINdeclare i int default 0; set i0;while i<1…...

centos安装nginx实操记录(加安全配置)
1.下载与安装 yum -y install nginx2.启动命令 /usr/sbin/nginx -c /etc/nginx/nginx.conf3.新建配置文件 cd /etc/nginx/conf.d vim index.conf配了一个负责均衡,如不需要,可将 server localhost: 多余的去掉 upstream web_server{server localhost…...
【中等】49. 字母异位词分组
原题链接:https://leetcode.cn/problems/group-anagrams 49. 字母异位词分组 给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs [“…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...