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

day58 第十一章:图论part08

拓扑排序精讲

关键:

先找到入度为0的节点,把这些节点加入队列/结果,然后依次循环再找。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {int m, n, s, t;cin >> n >> m;vector<int> inDegree(n, 0); // 记录每个文件的入度unordered_map<int, vector<int>> umap;// 记录文件依赖关系vector<int> result; // 记录结果while (m--) {// s->t,先有s才能有tcin >> s >> t;inDegree[t]++; // t的入度加一umap[s].push_back(t); // 记录s指向哪些文件}queue<int> que;for (int i = 0; i < n; i++) {// 入度为0的文件,可以作为开头,先加入队列if (inDegree[i] == 0) que.push(i);//cout << inDegree[i] << endl;}// int count = 0;while (que.size()) {int  cur = que.front(); // 当前选中的文件que.pop();//count++;result.push_back(cur);vector<int> files = umap[cur]; //获取该文件指向的文件if (files.size()) { // cur有后续文件for (int i = 0; i < files.size(); i++) {inDegree[files[i]] --; // cur的指向的文件入度-1if(inDegree[files[i]] == 0) que.push(files[i]);}}}if (result.size() == n) {for (int i = 0; i < n - 1; i++) cout << result[i] << " ";cout << result[n - 1];} else cout << -1 << endl;}

dijkstra(朴素版)精讲

不能处理负权重,贪心算法,minDist表示距离原点最近的距离。

跟prim一样

#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main(){int n,m,s,e,v;cin>>n>>m;vector<vector<int>> grid(n+1,vector<int>(n+1, INT_MAX));for(int i=0;i<m;i++){cin>>s>>e>>v;grid[s][e]=v;}vector<bool> visited(n+1, false);vector<int> minDist(n+1, INT_MAX);int start = 1;minDist[start] = 0;for(int i=0;i<n;i++){int cur = -1;int minVal = INT_MAX;//1.选择未到过的且距离起始点最近车站for(int j=1;j<=n;j++){if(!visited[j] && minDist[j]<minVal){cur = j;minVal = minDist[j];}}if(cur == -1) {break;}//2.到达该车站visited[cur] = true;//3.更新minDistfor(int j=1;j<=n;j++){if(!visited[j] && grid[cur][j]!=INT_MAX && minDist[cur]+grid[cur][j]<minDist[j]){minDist[j] = minDist[cur]+grid[cur][j];}}// cout<<"cur="<<cur<<endl;// for(int k=1;k<=n;k++){//     cout<<minDist[k]<<" ";// }// cout<<endl;}int count = 0;for(int i=1;i<=n;i++){if(visited[i]){count++;}}if(count==n){cout<<minDist[n]<<endl;}else{cout<<-1<<endl;}}

相关文章:

day58 第十一章:图论part08

拓扑排序精讲 关键&#xff1a; 先找到入度为0的节点&#xff0c;把这些节点加入队列/结果&#xff0c;然后依次循环再找。 #include <iostream> #include <vector> #include <queue> #include <unordered_map> using namespace std; int main() {int …...

网络安全-openssl工具

OpenSSl是一个开源项目&#xff0c;包括密码库和SSL/TLS工具集。它已是在安全领域的事实标准&#xff0c;并且拥有比较长的历史&#xff0c;现在几乎所有的服务器软件和很多客户端都在使用openssl&#xff0c;其中基于命令行的工具是进行加密、证书管理以及测试最常用到的软件。…...

Java面试第六山!《MySQL基础知识点》

一、引言 MySQL 作为一款广泛使用的开源关系型数据库管理系统&#xff0c;在软件开发领域占据着重要地位。无论是小型项目还是大型企业级应用&#xff0c;都能看到 MySQL 的身影。今天就来和大家分享 MySQL 的相关知识&#xff0c;帮助大家更好地应对日常开发和面试。 二、My…...

云计算中的API网关是什么?为什么它很重要?

在云计算架构中&#xff0c;API网关&#xff08;API Gateway&#xff09;是一个重要的组件&#xff0c;主要用于管理、保护和优化不同服务之间的接口&#xff08;API&#xff09;通信。简单来说&#xff0c;API网关就像是一个中介&#xff0c;它充当客户端和后端服务之间的“桥…...

【WebGL】fbo双pass案例

双pass渲染案例&#xff08;离线渲染一个三角面&#xff0c;然后渲染到一个占满屏幕的矩阵上&#xff09; 离线渲染如何需要开启深度测试的话&#xff0c;需要额外操作&#xff0c;这里不展开 <!DOCTYPE html> <html lang"en"><head><meta ch…...

Unity面板介绍_层级面板(23.1.1)

一、Inspector(检视面板) 显示当前选定游戏对象附加的组件及其属性信息。为重要游戏物体选择图标 二、面板详情...

详解Nginx 配置

一、Nginx 介绍 Nginx 是一款轻量级的 Web 服务器 / 反向代理服务器及电子邮件&#xff08;IMAP/POP3&#xff09;代理服务器。它由俄罗斯的程序设计师 Igor Sysoev 所开发&#xff0c;自 2004 年发布以来&#xff0c;凭借其高性能、低内存消耗、高并发处理能力等特点&#xf…...

数据库系统概念

1. 绪论 数据库的基本概念: 数据(data): 数据库中存储的基本对象, 可以是文字, 声音, 图片, 视频等。 数据库(DB): 概括来说就是永久存储, 有组织, 可共享的大量数据的集合。 数据库管理系统(DBMS): 和操作系统一样是计算机基础软件, 主要有数据定义语言(DDL, 对数据对象的组…...

51单片机学习之旅——定时器

打开软件 1与其它等于其它&#xff0c;0与其它等于0 1或其它等于1&#xff0c;0或其它等于其它 TMODTMOD&0xF0;//0xF01111 0000进行与操作&#xff0c;高四位保持&#xff0c;低四位清零&#xff0c;高四位定时器1&#xff0c;低四位定时器0 TMODTMOD|0x01;//0x010000 0…...

一台服务器将docker image打包去另一天服务器安装这个镜像

一台服务器将docker image打到去另一天服务器安装这个镜像 1. 打包2.另一台服务器执行 1. 打包 docker save -o nebula-graph-studio.tar harbor1.vm.example.lan/dockerio/vesoft/nebula-graph-studioxxx.tar 是打包好的文件 后面的是 docker image 2.另一台服务器执行 docke…...

QT串口通信之二,实现单个温湿度传感器数据的采集(采用Qt-modbus实现)

接上 QT串口通信之一,实现单个温湿度传感器数据的采集 上述文章中用QSerialPort实现了温湿度传感器的采集,实际上比较麻烦的,因为需要自定义解析帧, 接下来,用Qt-modbus-封装度更高的协议,来实现温湿度的采集; #include "MainWindow.h" #include "ui_M…...

基于SpringBoot的校园消费点评管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…...

【小沐学Java】VSCode搭建Java开发环境

文章目录 1、简介2、安装VSCode2.1 简介2.2 安装 3、安装Java SDK3.1 简介3.2 安装3.3 配置 4、安装插件Java Extension Pack4.1 简介4.2 安装4.3 配置 结语 1、简介 2、安装VSCode 2.1 简介 Visual Studio Code 是一个轻量级但功能强大的源代码编辑器&#xff0c;可在桌面上…...

《操作系统 - 清华大学》8 -4:进程管理:进程控制结构

深度剖析进程控制块&#xff1a;操作系统进程管理的核心关键 在操作系统的复杂体系中&#xff0c;进程控制块&#xff08;PCB&#xff09;是实现高效进程管理的关键所在。接下来&#xff0c;将从多个维度深入剖析进程控制块&#xff0c;帮助更好地理解其在操作系统中的重要作用…...

RPC 框架项目剖析

RPC 框架项目剖析 说明 本文用于梳理一个 rpc项目的实现细节&#xff0c;此项目基于cpp语言 大概三千行左右&#xff0c;用于学习目的。 项目链接&#xff1a;rpc项目 项目底层类 1.抽象消息类 描述&#xff1a; 各种消息的基类 属性&#xff1a; 消息id&#xff0c;消息类型…...

C++ Boost面试题大全及参考答案

目录 boost::thread_group 如何实现批量线程管理? 解释 boost::asio 中 proactor 模式的设计原理 使用 boost::atomic 实现无锁环形缓冲区 boost::mutex 与 std::mutex 在异常安全上的差异 如何用 boost::condition_variable 实现生产者 - 消费者模型 当 boost::shared_p…...

关于Transparent native-to-ascii conversion

1、功能 自动转换ASCII编码&#xff0c;即在文件系统上&#xff0c;文件的编码格式为ascii编码&#xff0c;在编辑器&#xff08;idea/pycharm&#xff09;中&#xff0c;其展现结果为配置的编码格式&#xff0c;仅展现方便阅读 使用UTF-8并勾选自动转换ASCII编码结果&#x…...

js数据类型检测

JavaScript的数据类型检测 typeof操作符 适用场景 基本数据类型快速判断&#xff1a;适用于快速判断变量是否为number、string、boolean、undefined、function等基本数据类型。比如在函数参数检查中&#xff0c;若要求传入数字参数&#xff0c;可用typeof来初步判断。函数类型…...

go 模块管理

go version 查看版本 go version go1.21.12 windows/amd64 需要保证:go的版本升级为1.11以上,go mod依赖的最底版本 go env 查看go的环境变量 go env 开启go mod # 标识开启go的模块管理 set GO111MODULE=on GO111MODULE有三个值:off, on和auto(默认值)。 GO111M…...

记一次复杂分页查询的优化历程:从临时表到普通表的架构演进

1. 问题背景 在项目开发中&#xff0c;我们需要实现一个复杂的分页查询功能&#xff0c;涉及大量 IP 地址数据的处理和多表关联。在我接手这个项目的时候,代码是这样的 要知道代码里面的 ipsList 数据可能几万条甚至更多,这样拼接的sql,必然是要内存溢出的,一味地扩大jvm参数不…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...