算法训练 | 图论Part8 | 117. 软件构建、47. 参加科学大会
目录
117. 软件构建
拓扑排序法
47. 参加科学大会
dijkstra法
117. 软件构建
-
题目链接:117. 软件构建
-
文章讲解:代码随想录
拓扑排序法
-
代码一:拓扑排序
#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;}
47. 参加科学大会
-
题目链接:47. 参加科学大会(第六期模拟笔试)
-
文章讲解:代码随想录
dijkstra法
-
代码一:dijkstra
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2] = val;}int start = 1;int end = n;// 存储从源点到每个节点的最短距离std::vector<int> minDist(n + 1, INT_MAX);// 记录顶点是否被访问过std::vector<bool> visited(n + 1, false);minDist[start] = 0; // 起始点到自身的距离为0for (int i = 1; i <= n; i++) { // 遍历所有节点int minVal = INT_MAX;int cur = 1;// 1、选距离源点最近且未访问过的节点for (int v = 1; v <= n; ++v) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}visited[cur] = true; // 2、标记该节点已被访问// 3、第三步,更新非访问节点到源点的距离(即更新minDist数组)for (int v = 1; v <= n; v++) {if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + grid[cur][v];}}}if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点else cout << minDist[end] << endl; // 到达终点最短路径}
相关文章:
算法训练 | 图论Part8 | 117. 软件构建、47. 参加科学大会
目录 117. 软件构建 拓扑排序法 47. 参加科学大会 dijkstra法 117. 软件构建 题目链接:117. 软件构建 文章讲解:代码随想录 拓扑排序法 代码一:拓扑排序 #include <iostream> #include <vector> #include <queue> …...
编程从零基础到进阶(更新中)
题目描述 依旧是输入三个整数,要求按照占8个字符的宽度,并且靠左对齐输出 输入格式 一行三个整数,空格分开 输出格式 输出它们按格式输出的效果,占一行 样例输入 123456789 -1 10 样例输出 123456789-1 10 #include "stdio.…...
MySQL运维实战之ProxySQL(9.6)SQL黑名单
作者:俊达 利用mysql_query_rules表中的error_msg字段,可以实现SQL黑名单的功能。如果规则设置了error_msg,当SQL语句匹配这条规则时,proxysql会直接将error_msg的内容返回给客户端。 当遇到一些大查询严重影响数据库性能时&…...
深入了解MySQL中的innodb_lock_wait_timeout
引言 在数据库管理中,确保数据的一致性和完整性是至关重要的。MySQL的InnoDB存储引擎通过行级锁定机制来实现这一点。然而,当多个事务同时操作数据库时,可能会出现锁等待的情况。了解并合理配置innodb_lock_wait_timeout参数,对于…...
102.qt qml-最全Table交互之多列固定、行列拖拽、自定义委托、标题交互使用教程
自定义实现的Table控件,支持跨qt版本,兼容qt5,qt6! 截图如下所示: 黑色风格如下所示: 视频演示入口:Qt QML QianWindowV2.5(新增曲线综合示例、QML最全Table交互示例、支持qt5/qt6)_哔哩哔哩_bilibili 1.示例页面入口…...
文章管理小程序的设计
管理员账户功能包括:系统首页,个人中心,作者管理,文章管理,文章分类管理,论坛,系统管理 微信端账号功能包括:系统首页,文章,论坛,我的 开发系统…...
Ubuntu22.04安装NIVIDIA显卡驱动总结
1.首先在安装驱动时需要判断系统有无GPU以及GPU的型号 可以参考这篇文章: https://blog.51cto.com/u_13171517/8814753#:~:textubuntu%20%E7%B3%BB%E7%BB%9F%20%E6%80%8E%E4%B9%88%E5%88%A4%E6%96%AD%E7%B3%BB%E7%BB%9F%E6%9C%89%E6%B2%A1%E6%9C%89GPU%201%20%E6%…...
Redis的配置优化、数据类型、消息队列
文章目录 一、Redis的配置优化redis主要配置项CONFIG 动态修改配置慢查询持久化RDB模式AOF模式 Redis多实例Redis命令相关 二、Redis数据类型字符串string列表list集合 set有序集合sorted set哈希hash 三、消息队列生产者消费者模式发布者订阅者模式 一、Redis的配置优化 redi…...
数据结构之初始二叉树(2)
找往期文章包括但不限于本期文章中不懂的知识点: 个人主页:我要学编程(ಥ_ಥ)-CSDN博客 所属专栏:数据结构(Java版) 二叉树的前置知识(概念、性质、、遍历) 通过上篇文章的学习,我们…...
如何预防最新的baxia变种勒索病毒感染您的计算机?
引言 在当今数字化时代,网络安全威胁层出不穷,其中勒索病毒已成为企业和个人面临的重大挑战之一。近期,.baxia勒索病毒以其高隐蔽性和破坏性引起了广泛关注。本文将详细介绍.baxia勒索病毒的特点、传播方式,并给出相应的应对策略…...
git列出提交记录的文件路径
一、如何列出某次提交记录中修改过/新增的文件? 方法1:使用 git diff-tree 命令来查看某个提交记录中修改过/新增的文件。具体来说,你可以使用以下命令: git diff-tree --no-commit-id --name-only -r <commit-hash>命令解…...
微信小程序密码 显示隐藏 真机兼容问题
之前使用type来控制,发现不行,修改为password属性即可 <van-fieldright-icon"{{passwordType password? closed-eye:eye-o}}"model:value"{{ password }}"password"{{passwordType password ? true: false}}"borde…...
C# 中,使用 LINQ 示例 备忘
语言集成查询 (LINQ) 是一系列直接将查询功能集成到 C# 语言的技术统称。 数据查询历来都表示为简单的字符串,没有编译时类型检查或 IntelliSense 支持。 此外, … 对于编写查询的开发者来说,LINQ 最明显的“语言集成”部分就是查询表达式。 …...
GaussDB DWS 详解
文章目录 GaussDB DWS 详解一、简介二、DWS的分布式架构架构概述关键组件 三、分布式查询数据查询流程SQL执行的示例 批注:本文引鉴了Forlogen博主的一些内容,并加以补充,以供学习了解。 GaussDB DWS 详解 一、简介 DWS(Data Warehouse Ser…...
【256 Days】我的创作纪念日
目录 🌼01 机缘 🌼02 收获 🌼03 日常 🌼04 成就 🌼05 憧憬 最近收到官方来信, 突然发现,不知不觉间,距离发布的第一篇博客已过256天,这期间我经历了春秋招、毕业答辩…...
3D云渲染工具对决:Maya与Blender的性能和功能深度比较
3D建模和动画制作已成为数字领域不可或缺的一环,无论是在影视特效的震撼场面,还是在游戏角色的生动表现,3D技术都扮演着至关重要的角色。而在这一领域,Maya和Blender这两款软件,以其强大的功能和广泛的应用,…...
spring.factories详解
spring.factories 是 Spring Boot 中一个重要的配置文件,它用于实现自动配置类和框架的扩展机制。这个文件通常位于项目的 resources/META-INF 目录下,并且遵循 Java 的 .properties 文件格式。以下是对 spring.factories 的详细解释: 自动配…...
从Docker Hub 拉取镜像一直失败超时?这些解决方案帮你解决烦恼
设置国内源: 提示:常规方案(作用不大) 阿里云提供了镜像源:https://cr.console.aliyun.com/cn-hangzhou/instances/mirrors 登录后你会获得一个专属的地址 使用命令设置国内镜像源:通过vim /etc/docker/d…...
【pbootcms】新环境搭建环境安装时发生错误
【pbootcms】新环境搭建环境安装时发生错误 提示一下内容: 登录请求发生错误,您可按照如下方式排查: 1、试着删除根目录下runtime目录,刷新页面重试 2、检查系统会话文件存储目录是否具有写入权限; 3、检查服务器环境pathinfo及伪静态规则配置; 先按照…...
C语言之qsort函数
一、qsort 1.库函数qsort qsort是库函数,直接可以用来排序数据,底层使用的是快速排序。 qsort函数可以排序任意类型的数据。 2.头文件 #include<stdlib.h> 3.参数讲解 void*类型的指针是无具体类型的指针,这种类型的指针的不能直接解…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...
