当前位置: 首页 > 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参数不…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...