当前位置: 首页 > news >正文

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

个人学习记录&#xff0c;代码难免不尽人意。 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.管道通信原理 特点&#xff1a; 1.它是半双工的&#xff08;即数据只能在一个方向上流动&#xff09;&#xff0c;具有固定的读端和写端。 2.它只能用于具有亲缘关系的进程之间通信&#xff08;也是父子进程或者…...

C#-单例模式

文章目录 单例模式的概述为什么会有单例模式如何创建单例模式1、首先要保证&#xff0c;该对象 有且仅有一个2、其次&#xff0c;需要让外部能够获取到这个对象 示例通过 属性 获取单例 单例模式的概述 总结来说&#xff1a; 单例 就是只有 一个实例对象。 模式 说的是设计模式…...

WSNs 安全技术

WSNs 多用于军事&#xff0c;特殊现场的警戒保护、商业区域的安防&#xff0c;作为任务型网 络&#xff0c;不仅要进行数据传输&#xff0c;而且要进行数据采集和融合&#xff0c;任务的协同控制等&#xff0c;如何 保证任务执行的机密性&#xff0c;数据产生的可靠性数据融合…...

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

Jmeter如何设置中文版

第一步&#xff1a;找到 apache-jmeter-5.4.3\bin目录下的 jmeter.properties 第二步:打开 三&#xff0c;ctrf 输入languageen&#xff0c;注释掉&#xff0c;增加以行修改如下 四&#xff0c;ctrs 保存修改内容&#xff0c;重新打开jmeter就可以了...

flutter自定义按钮-文本按钮

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

无涯教程-Android - CheckBox函数

CheckBox是可以由用户切换的on/off开关。为用户提供一组互不排斥的可选选项时,应使用复选框。 CheckBox 复选框属性 以下是与CheckBox控件相关的重要属性。您可以查看Android官方文档以获取属性的完整列表以及可以在运行时更改这些属性的相关方法。 继承自 android.widget.T…...

[Go版]算法通关村第十五关青铜——用4KB内存寻找重复元素

目录 题目&#xff1a;用4KB内存寻找重复元素思路分析&#xff1a;使用位存储如何存储这32000个整数&#xff1f;每个整数对应在位图中的存储状态举例如何判断是重复的&#xff1f;具体的步骤 复杂度&#xff1a;时间复杂度 O ( n ) O(n) O(n)、空间复杂度 O ( 1 ) O(1) O(1)Go…...

OJ练习第159题——消灭怪物的最大数量

消灭怪物的最大数量 力扣链接&#xff1a;1921. 消灭怪物的最大数量 题目描述 你正在玩一款电子游戏&#xff0c;在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist &#xff0c;其中 dist[i] 是第 i 个怪物与城市的 初始距离&#…...

Prometheus-Rules(规则)

文章目录 一、介绍二、配置 Prometheus 使用规则文件三、 规则文件语法规则文件语法全局Recording rules(记录规则)2 Alerting rules(警报规则)3 模板化如何使用四、检查规则文件语法五、发送警报通知一、介绍 Prometheus规则是一种逻辑表达式,可用于定义有关监控数据的逻…...

打卡智能中国(六):村里出了“飞行员”

提起返乡青年&#xff0c;你的第一印象是什么&#xff1f;失败、躺平、卷不动了&#xff1f; 我们在浙江、福建、青海等地&#xff0c;参观一些农业智能化项目时&#xff0c;陪同参观的“飞手”&#xff0c;高兴地跟我们分享自己的心路历程&#xff1a; 在家门口做农业无人机操…...

自动化运维工具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批量插入大量数据的方法

使用存储过程进行插入&#xff0c; 在navicate中示例如下&#xff1a; 输入需要的参数点击完成 在begin end中输入代码&#xff0c;示例代码如下 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配了一个负责均衡&#xff0c;如不需要&#xff0c;可将 server localhost: 多余的去掉 upstream web_server{server localhost…...

【中等】49. 字母异位词分组

原题链接&#xff1a;https://leetcode.cn/problems/group-anagrams 49. 字母异位词分组 给你一个字符串数组&#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs [“…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...