1599 - Ideal Path (UVA)
题目链接如下:
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4474
这道题也是看了刘汝佳的思路才写出来的....
代码如下:
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
#include <map>
const int maxx = 100005;
const int maxColor = 1e9 + 1;
// #define debugstruct node{int id, color;node(int _id, int _color): id(_id), color(_color){}
};
int n, m, u, v, c, k, curr, minn;
std::map<int, std::vector<node>> mp;
int d[maxx], pre[maxx], preColor[maxx];
bool vis[maxx];void bfs1(){std::deque<int> dq;dq.push_back(n);d[n] = 0;vis[n] = true;while (!dq.empty()){curr = dq.front();dq.pop_front();for (int i = 0; i < mp[curr].size(); ++i){int temp = mp[curr][i].id;if (!vis[temp]){d[temp] = d[curr] + 1;vis[temp] = true;dq.push_back(temp);}}}
}void bfs2(){std::deque<int> dq;dq.push_back(1);while (!dq.empty()){curr = dq.front();dq.pop_front();minn = maxColor;for (int i = 0; i < mp[curr].size(); ++i){int temp = mp[curr][i].id;if (d[temp] == d[curr] - 1){minn = std::min(minn, mp[curr][i].color);}}for (int i = 0; i < mp[curr].size(); ++i){int temp = mp[curr][i].id;if (d[temp] == d[curr] - 1 && mp[curr][i].color == minn){if (!pre[temp]){dq.push_back(temp);}if (!pre[temp] || preColor[temp] > minn){pre[temp] = curr;preColor[temp] = minn;}}}}
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifwhile (scanf("%d %d", &n, &m) == 2){mp.clear();std::fill(d, d + n + 1, -1);std::fill(vis, vis + n + 1, false);std::fill(pre, pre + n + 1, 0);std::fill(preColor, preColor + n + 1, -1);while (m--){scanf("%d %d %d", &u, &v, &c);if (u != v){mp[u].push_back(node(v, c));mp[v].push_back(node(u, c));}}bfs1();bfs2();std::vector<int> path;curr = n;do {path.push_back(preColor[curr]);curr = pre[curr];} while (curr != 1);reverse(path.begin(), path.end());printf("%d\n", path.size());for (int i = 0; i < path.size(); ++i){printf("%d%s", path[i], i == path.size() - 1 ? "\n" : " ");}}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}
相关文章:
1599 - Ideal Path (UVA)
题目链接如下: https://onlinejudge.org/index.php?optioncom_onlinejudge&Itemid8&category448&pageshow_problem&problem4474 这道题也是看了刘汝佳的思路才写出来的.... 代码如下: #include <cstdio> #include <deque&…...
计算机网络(超级详细笔记)
使用教材计算机网络(第8版)(谢希仁) 第一章:概述 第二章:物理层 第三章:数据链路层 第四章:网络层 第五章:运输层 第六章:应用层 目…...
老杨说运维 | 年末大讲回顾:运维的尽头也是大模型吗?
哈喽~朋友们,这么快又见面啦。前阵子我们给CEO老杨安排了一场年末大讲,主要是跟大家聊聊智能运维的“智”与“能”以及剖析时下热点----运维大模型。后台收到了不少朋友的反馈,小编看了大受鼓舞并暗下决心----新的一年,希望能多安…...
Unity 利用UGUI之Scrollbar制作进度条
在Unity中除了用Slider、Image做进度条,其实用Scrollbar也可以做进度条。 首先,在场景中新建一个Scrollbar组件和一个Text组件: 其次,创建模拟进度的一个脚本,Scrollbar_Progressbar.cs: using System.Collections; …...
MySQL之导入、导出
文章目录 1.navicat导入导出2.mysqldump命令导入导出2.1导出2.2导入 3.load data infile命令导入导出4.远程备份5.思维导图 1.navicat导入导出 使用Navicat工具导入t_log 共耗时 55s 2.mysqldump命令导入导出 2.1导出 导出表数据和表结构 语法: mysqldump -u用…...
【unity小技巧】FPS游戏实现相机的偏移震动、武器射击后退和后坐力效果
最终效果 文章目录 最终效果前言相机偏移震动相机震动脚本换弹节点震动 武器射击后退效果武器后坐力效果完结 前言 关于后坐力之前其实已经分享了一个:FPS游戏后坐力制作思路 但是实现起来比较复杂,如果你只是想要简单的实现,可以看看这个&…...
MINCO+汽车
规划典型的解决方法: 如何准确的描述他的动力学,实际上是对这个物理对象进行建模.(规划等于开环的控制,控制等于闭环的规划),规划系统要做到是假设已知系统模型的情况下去计算一些可能会影响比较好的 未来运动的指令,做未来运动轨迹的推演.对自己建模的情况下还需对环境有个比较…...
大模型机器人发展史:从VoxPoser、RT2到斯坦福Mobile ALOHA、Google机器人
前言 23年7月,我在朋友圈评估Google的RT2说道: “大模型正在革新一切领域啊,超帅,通过大模型不仅能理解“人话”,还能对“人话”进行推理,并转变为机器人能理解的指令,从而分阶段完成任务。回…...
Ubunutu18.04 ROS melodic 无人机 XTDrone PX4 Vins-Fuison 运行配置
一、PX4飞控EKF配置 PX4默认使用的EKF配置为融合GPS的水平位置与气压计高度。如果我们想使用视觉定位,就需要把修改配置文件。让EKF融合来自mavros/vision_pose/pose的数据 1.1修改rcS配置文件 gedit ~/PX4_Firmware/ROMFS/px4fmu_common/init.d-posix/rcS 通过注…...
Linux 常见服务配置
笔记所以内容很多,建议选择性看看 SSH Secure Shell 用于与服务器建立安全的连接 对应服务 sshd 注意:配置文件 配制文件修改需要重启或重载sshd服务才能生效 systemctl sshd reload # 重载 sshd 配置文件 systemctl sshd restart # 重启 ssh…...
Flutter基础
一、关键字 class:用于定义一个新的类; extends: 用于指定一个类继承另一个类; mixin: 用于将一个类的代码片段添加到另一个类中,实现代码复用; abstract: 用于声明一个抽象类或抽象方法,不能直接实例化&a…...
MySQL-数据库概述
数据库相关概念: 数据库(DateBase)简称DB,就是一个存储数据的仓库,数据有组织的进行存储。 数据库分为关系型数据库简称RDBMS和非关系型数据库 关系型数据库简称RDBMS:建立在关系模型的基础上,由多张相互连接的二维表组成的数据库.简单来说…...
HTML---JQurey的基本使用
文章目录 前言一、pandas是什么?二、使用步骤 1.引入库2.读入数据总结 本章目标 (1)能够搭建jQuery开发环境 (2)使用ready( )方法加载页面、掌握jQuery语法 使用addClass( )方法和css( )方法为元素添加CSS样式使用n…...
搜索docker镜像
要查看Docker镜像库,可以使用docker search命令。 docker search <关键词>例如,如果你想要查找名为nginx的镜像,可以执行以下命令: docker search nginx命令执行后,将会列出所有与关键词nginx相关的Docker镜像…...
旋变检测AD2s1205手册学习笔记
旋变故障检测故障表 信号丢失检测 检测原理:任一旋变输入(正弦或余弦)降至指定的LOS正弦/余弦阈值 以下时,器件会检测到信号丢失(LOS)。AD2S1205通过将 监视信号与固定最小值进行比较检测此点 丢失的效果表现:LOS由DOS和LOT引脚均闩锁为逻辑…...
【温故而知新】JavaScript的防抖与节流
一、概念 JavaScript中的防抖(debounce)和节流(throttle)是用于控制函数执行频率的技术。 防抖:当一个事件连续触发时,防抖技术将只执行最后一次触发事件的函数调用。换句话说,只有在停止触发…...
C++模板——(3)类模板
归纳编程学习的感悟, 记录奋斗路上的点滴, 希望能帮到一样刻苦的你! 如有不足欢迎指正! 共同学习交流! 🌎欢迎各位→点赞 👍 收藏⭐ 留言📝 勤奋,机会,乐观…...
深度学习中Epoch和Batch Size的关系
在深度学习中,Epoch(周期)和 Batch Size(批大小)是训练神经网络时经常使用的两个重要的超参数。它们之间的关系是通过以下方式连接的: Epoch(周期): Epoch 表示整个训练…...
Python采集微博评论做词云图
嗨喽~大家好呀,这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 环境使用: Python 3.10 Pycharm 第三方模块使用: import requests >>> pip install requests import wordcloud >>> pip install wordclou…...
一文详解VScode 的远程开发
VS code登录服务器后进行编码和调试,VS code上的所有功能都可以使用,和在本地开发基本无区别。 一、配置免密远程登录 因为是要远程登录,那么需要通过使用ssh进行密钥对登录,这样每次登录服务器就可以不用输入密码了。 先来一句官…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
yaml读取写入常见错误 (‘cannot represent an object‘, 117)
错误一:yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因,后面把yaml.safe_dump直接替换成yaml.dump,确实能保存,但出现乱码: 放弃yaml.dump,又切…...
写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里
写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...
Django RBAC项目后端实战 - 03 DRF权限控制实现
项目背景 在上一篇文章中,我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统,为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...
验证redis数据结构
一、功能验证 1.验证redis的数据结构(如字符串、列表、哈希、集合、有序集合等)是否按照预期工作。 2、常见的数据结构验证方法: ①字符串(string) 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...
当下AI智能硬件方案浅谈
背景: 现在大模型出来以后,打破了常规的机械式的对话,人机对话变得更聪明一点。 对话用到的技术主要是实时音视频,简称为RTC。下游硬件厂商一般都不会去自己开发音视频技术,开发自己的大模型。商用方案多见为字节、百…...
【题解-洛谷】P10480 可达性统计
题目:P10480 可达性统计 题目描述 给定一张 N N N 个点 M M M 条边的有向无环图,分别统计从每个点出发能够到达的点的数量。 输入格式 第一行两个整数 N , M N,M N,M,接下来 M M M 行每行两个整数 x , y x,y x,y,表示从 …...
