【图论】想越狱的小衫

news/2024/7/24 14:55:02/

题目描述

这次小杉来到了经典美剧《越狱》的场景里……他被抓起来了(-.-干嘛幻想这么郁闷的场景……)。

小杉身为新一代的Scofield,在挖了半个月之后终于挖通牢房里的地道。

在地道里,无数的管道路线困惑了他。

小杉看了看自己的纹身,明白了整个管道网是由N个小房间和若干小房间之间的单向的管道组成的。

小房间编号为不超过N的正整数。

对于某个管道,小杉只能在人品不超过一定程度时通过。

小杉一开始在房间1,现在小杉想知道,每个小房间他最多能够以人品多少的状态到达。

注意,小杉的人品在出发以后是不会改变的。

输入

每组测试数据的第一行有一个正整数N(1<=N<=2000)。

接下来若干行描述管道,每行三个正整数A,B,R(1<=A,B<=N),表示A房间有一条到达B房间的管道,且小杉的人品不超过R时可以通过(注意从B房间不可由此管道到达A房间,即管道是单向的)
整个输入数据以一行0 0 0结束

特别地,对于30%的数据,有N<=100,对于100%的数据,有N<=2000.

输出

    对每组测试数据输出N-1行,分别表示对于2到N号的小房间,小杉最多能够以人品多少的状态到达(到达不了为0)。

样例输入

4
1 2 30
1 3 20
2 3 25
3 4 30
2 4 20
0 0 0

样例输出

30
25
25

提示

来源

#include<bits/stdc++.h>
using namespace std;
struct edge{int v,w;bool operator<(edge a)const{return w<a.w;}
}now,temp;
int dis[10005],n,m;
bool vis[10005];
vector<edge>a[10005];
void dijkstra(){memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));dis[1]=0x3f3f3f3f;priority_queue<edge>q;q.push({1,dis[1]});while(!q.empty()){now=q.top();q.pop();if(vis[now.v]) continue;vis[now.v]=1;int len=a[now.v].size();for(int i=0;i<len;i++){temp=a[now.v][i];if(min(dis[now.v],temp.w)>dis[temp.v]){dis[temp.v]=min(dis[now.v],temp.w);q.push({temp.v,dis[temp.v]});}}}}
int main(){cin>>n;int u,v,w;while(1){cin>>u>>v>>w;if(u==0&&w==0&&v==0) break;a[u].push_back({v,w});}dijkstra();for(int i=2;i<=n;i++){cout<<dis[i]<<endl;}return 0;}

图论-最短路


http://www.ppmy.cn/news/75266.html

相关文章

游戏洞察丨自来水还是井水,后流量时代的私域挑战

流量生意本质上是买卖用户浏览时间的生意&#xff0c;如果用户增长到顶&#xff0c;那就意味着供给到顶。对比 2021 年&#xff0c;2022 年的游戏出海在谷歌和 Facebook 上投入的广告成本几乎翻了一倍。新晋“渠道王者”TikTok 逐渐走进大家的视野。该现象背后的原因在于&#…

MySQL数据库最常见的6种故障的排除方法

MySQL数据库最常见的6中故障的排除方法 1.MySQL无法启动 2.MySQL连接不上 3.MySQL打开文件失败 4.MySQL挂起&#xff08;hung&#xff09; 5.MySQL崩溃&#xff08;crash&#xff09; 6.忘记用户密码 1.MySQL无法启动 1.无法访问系统资源 2.参数设置错误 无法访问系统…

ffmpeg命令行工具源码之结构体分析1-命令行参数(未完结,持续更新)

前言 ffmpeg作为多媒体文件转换工具&#xff0c;至少需要有一个要转换的输入文件信息&#xff08;不仅仅是普通文件&#xff0c;还可以是摄像头设备&#xff0c;网络流等&#xff09;&#xff0c;和通常至少需要一个输出格式的文件&#xff08;输出文件不仅仅指普通的文件&…

【SQL】MySQL的数据类型

MySQL的数据类型 MySQL是一种广泛使用的关系型数据库管理系统&#xff0c;它支持各种数据类型&#xff0c;包括数字、字符串、日期和时间等。在MySQL中&#xff0c;数据类型是用来定义表中列的类型&#xff0c;它决定了表中的数据如何被存储和操作。 数字类型 MySQL支持多种…

完犊子!原单位的离职证明丢了,下周要入职了,用AI做一个行不行?

弄丢了离职证明怎么办&#xff1f; 一位网友哀叹&#xff1a; 完犊子&#xff01;原单位的离职证明丢了&#xff0c;下周要入职了&#xff0c;现在怎么办&#xff1f;用AI做一个行不行&#xff1f; 有相同经历的网友安慰他&#xff0c;离职证明没了没事&#xff0c;新公司会要求…

格式化数据写入sprintf的用法

sprintf 是一个常见的 C 语言函数&#xff0c;用于将格式化的数据写入字符串缓冲区中。它的原型如下&#xff1a; int sprintf(char *str, const char *format, …); sprintf 函数将按照指定的格式 format 将数据写入字符串 str 中&#xff0c;并返回写入的字符数&#xff08;不…

linux动态库版本控制

文章目录 1. 动态库相关概念2. ldd 查看依赖项3. 动态链接器 ld.so的加载路径4. 动态版本库版本控制5. ldconfig自动更新soname到linkname6. 可执行程序的执行过程 linux 动态库版本控制 1. 动态库相关概念 Soname、linkname和realname都是在Linux系统下与共享库&#xff08;s…

firewalld防火墙

文章目录 firewalld概述firewalld 与 iptables 的区别firewalld 区域的概念firewalld防火墙预定义了9个区域 firewalld数据处理流程firewalld检查数据包的源地址的规则 firewalld防火墙的配置方法常用的firewall-cmd 命令选项区域管理服务管理端口管理设置地址转换 firewalld概…

大学4年做出来这个算不算丢人

前言&#xff1a;相信看到这篇文章的小伙伴都或多或少有一些编程基础&#xff0c;懂得一些linux的基本命令了吧&#xff0c;本篇文章将带领大家服务器如何部署一个使用django框架开发的一个网站进行云服务器端的部署。 文章使用到的的工具 Python&#xff1a;一种编程语言&…

【计算机网络基础】辨析专题④ 网络层

文章目录 重要简写重要概念重要简写 1.IP——网际协议 2.APR——地址解析协议 3.ICMP——网际控制报文协议 4.IGMP——网际组管理协议 5.HLB——集线器 6.ICANN——互联网名字和数字分配机构 7.CIDR——无分类域间路由选择 8.RARP——逆地址解析协议 9.IGP——内部网关…

Vue安全

vue的安全措施 HTML内容 不论使用模板还是渲染函数&#xff0c;内容都会被自动转义。也就是说对于这份模板&#xff1a; <h1>{{ userProvidedString }}</h1>如果 userProvidedString 包含了&#xff1a; <script>alert("hi")</script>则…

使用TTL管理ClickHouse数据生命周期

ClickHouse中数据随着时间变迁可能需要定期移动、删除或汇总数据。这依赖数据保留需求和历史数据的SLA(服务等级协议)&#xff0c;可以对历史数据采用更高的压缩级别节约更多空间。举例&#xff0c;对于超过1个月的数据采用lz4hc压缩算法&#xff0c;则需要DDL语法使用TTL的REC…

MyBatis动态推理参数类型

前言 思考一个问题&#xff0c;前面的#{}和${}的区别中&#xff0c;我们知道了#{}&#xff0c;MyBatis底层调用的是preparestatement这种预编译的方式&#xff0c;这种方式sql语句会预先编程 select * from t_user where id ?这种形式&#xff0c;随后调用setInt(),setString…

Postman传递@requestbody标注的List集合的传参遇到的问题

Postman传递requestbody标注的List集合的传参遇到的问题 引子如何测试以及遇到的问题参考文献 引子 我们想测试如下接口 RequestMapping(value "saveMessageRecover", method RequestMethod.POST) ResponseBody public AjaxMessage saveMessageRecover(RequestBod…

Robot Dynamics Lecture Notes学习笔记之关节空间动力学控制

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 关节空间动力学 关节空间动力学控制关节阻抗调节重力补偿逆动力学控制 关节空间动力学控制 目前的工业机器人几乎完全依赖于关节位置控制的概念。它们建立在PID控制器的基础…

(学习日记)AD学习 #3

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…

认识常见中间件-redis(三)-redis缓存更新策略

redis缓存更新策略主要有三种:Cache Aside Pattern、Read/Write Through Pattern、Write Behind Caching Pattern Cache Aside Pattern&#xff08;旁路缓存&#xff09; Cache Aside策略是最常用的&#xff0c;应用程序直接与「数据库、缓存」交互&#xff0c;并负责对缓存的…

【JDK】module模块系统

JDK9新特性-module模块系统 在Sources Root下新建module-info.java&#xff0c;内容格式如下所示 module modulename {//模块指令 }modulename具有唯一性一个工程&#xff0c;即使是不同的Sources Root&#xff0c;仅能存在一个module-info.java模块体内可以保留空内容或者模…

QT客户端外包开发的特点

QT是一种跨平台的C应用程序开发框架&#xff0c;主要用于开发图形用户界面(GUI)应用程序。它提供了一套丰富的类库和工具&#xff0c;可以帮助开发者快速构建高质量、可扩展、易于维护的应用程序。今天和大家分享一下QT的主要特点和注意的问题&#xff0c;希望对大家有所帮助。…

分享7款优质免费的Figma“中文插件”

今天我要向你们分享一些 Figma 的“中文插件”&#xff0c;这些插件不仅功能强大&#xff0c;而且免费使用&#xff0c;非常方便&#xff0c;而且是完全中文的页面使用起来非常便捷&#xff0c;可以大大提高设计师的效率和体验。 1、「平面 3D」 插件 首先是平面 3D 插件。该…