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

acwing 4275. Dijkstra序列

题目背景

输入

在这里插入图片描述
在这里插入图片描述

输出

在这里插入图片描述

在这里插入图片描述

完整代码
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[1010],dist[1010],g[1010][1010],st[1010];int dij(int u){memset(st,0,sizeof st);memset(dist,0x3f,sizeof dist);dist[u]=0;for(int i=0;i<n;i++){int t=a[i];for(int j=1;j<=n;j++){if(!st[j]&&dist[j]<dist[t]) return 0;}for(int j=1;j<=n;j++){dist[j]=min(dist[j],dist[t]+g[t][j]);}st[t] = 1;}return 1;
}int main(){cin>>n>>m;memset(g,0x3f,sizeof g);for(int i=0;i<m;i++){int v,w,r;cin>>v>>w>>r;g[v][w]=g[w][v]=min(g[v][w],r);}cin>>k;for(int i=0;i<k;i++){for(int i=0;i<n;i++) cin>>a[i];cout<<(dij(a[0])?"Yes":"No")<<"\n";}return 0;
}

这道题就是看每次dij方法和他给的点是不是一样近。
dij方法好像都是开那几个数组,dij函数一样,大概也就邻接表 邻接矩阵 堆优化几种吧。

http://www.xdnf.cn/news/6361.html

相关文章:

  • 二叉树复习(C语言版)
  • 国标GB28181视频平台EasyGBS打造交通道路/停车场/公共场所违章视频监控解决方案
  • keil编译时报错:error:Could not open file .\***\core_cm3.o(最有用的方法没有之一!!!)
  • 代码随想录算法训练营第三十九天(打家劫舍专题) | 198.打家劫舍、213.打家劫舍II、337.打家劫舍III
  • Windows更新暂停七天关键注册表
  • 无人机箱号识别系统结合5G技术的应用实践
  • 数字IC后端零基础入门基础理论(Day2)
  • AD 间距规则与布线规则
  • GaussDB 实例 gsql 连接方式详解
  • 在python中使用Json提取数据
  • [思维模式-38]:看透事物的关系:什么是事物的关系?事物之间的关系的种类?什么是因果关系?如何通过数学的方式表达因果关系?
  • 第五部分:第三节 - Express.js 框架入门:厨房的流程管理系统
  • 力扣-102.二叉树的层序遍历
  • 在 Ubuntu 20.04.6 LTS 中将 SCons 从 3.1.2 升级到 4.9.1
  • c++和c的不同
  • 【复刻】人工智能技术应用如何影响企业创新(2007-2023年)
  • 鸿蒙Next API17学习新特性之组件可见区域变化事件新增支持设置事件的回调参数,限制它的执行间隔
  • MATLAB 中常用的微分函数介绍
  • Redis的热Key问题如何解决?
  • 信息化项目绩效管理办法V5.0
  • 一篇解决Redis:持久化机制
  • 天拓四方盛装亮相第二十七届中国北京国际科技产业博览会
  • 未来软件开发趋势与挑战
  • 深入理解ThingsBoard的Actor模型
  • 基于Swim Transformer的脑癌MRI图像智能辅助诊断模型
  • Vue 图片预览功能(含缩略图)
  • 【Redis】集群
  • 第29节:现代CNN架构-Inception系列模型
  • 智能视觉检测技术:制造业质量管控的“隐形守护者”
  • Gartner《分布式和微服务架构中数据架构》学习心得