POJ 3169 Layout BellmanFord Dijkstra
一、心路历程
这一个题目写了三天,可以说是非常挣扎了,明明是例题,但是就是倔强着不去看书上的题解,WA了7次,TLE了4次。

写了不知道多少条测试用例,一遍一遍的过,一点一点的调试。

最后终于找到了规则
二、思路
1、题目要求1到N,必须按照顺序排,那么我们就可以认为 对每个 i >1,存在 i -1 到 i 的 0 的斥力
2、我们每一条A到B的排斥力P,看作B到A引力力 P * (-1)
3、规则1中 斥力,和 输入的斥力,都按照第二条规则,转化引力,然后不考虑斥力
4、用 BellmanFord算法,对转换成的和输入的引力集合,判断是否存在负圈,存在直接输出-1
5、不存在负圈,则直接对转换成的和输入的引力集合使用dijkstra算法,起点是1,如果d[N]大于1000000007(每条边最大值乘以边数,加7是为了防止边界出错),则输出-2,否则输出d[N]。
三、代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node
{int from, to, cost;Node(int from = 0, int to = 0, int cost = 0) : from(from), to(to), cost(cost) {}
};
vector<Node> nodes;
typedef pair<int, int> P;
vector<P> edges[1007];
int d[1007], N, inf = 0x3f3f3f3f, ML, MD, area[1007][1007];
bool used[1007];
void input()
{int from, to, cost;for (int i = 1; i <= ML; i++){scanf("%d%d%d", &from, &to, &cost);edges[from].push_back(P(cost, to));nodes.push_back(Node(from, to, cost));}for (int i = 1; i <= MD; i++){scanf("%d%d%d", &from, &to, &cost);edges[to].push_back(P(-cost, from));nodes.push_back(Node(to, from, -cost));}for (int i = 2; i <= N; i++){edges[i].push_back(P(0, i - 1));nodes.push_back(Node(i, i - 1, -1));}
}
bool bellmanFord(int s)
{bool flag = false;for (int i = 1; i <= N; i++){d[i] = inf;}d[s] = 0;for (int i = 1; i <= N; i++){for (int j = 0; j < nodes.size(); j++){if (d[nodes[j].from] + nodes[j].cost < d[nodes[j].to]){d[nodes[j].to] = d[nodes[j].from] + nodes[j].cost;if (i == N){flag = true;}}}}return flag;
}
void dijkstra(int s)
{for (int i = 1; i <= N; i++){d[i] = inf;used[i] = false;}d[s] = 0;priority_queue<P, vector<P>, greater<P>> que;que.push(P(0, s));while (!que.empty()){P current = que.top();que.pop();if (used[current.second] || current.first > d[current.second]){continue;}for (int i = 0; i < edges[current.second].size(); i++){P toEdge = edges[current.second][i];if (d[current.second] + toEdge.first < d[toEdge.second]){d[toEdge.second] = toEdge.first + d[current.second];que.push(P(d[toEdge.second], toEdge.second));}}}
}
void solve()
{if (bellmanFord(1)){printf("%d\n", -1);}else{dijkstra(1);if (d[N] > 1000000007){printf("%d\n", -2);}else{printf("%d\n", d[N]);}}
}
int main()
{scanf("%d%d%d", &N, &ML, &MD);input();solve();return 0;
}
相关文章:
POJ 3169 Layout BellmanFord Dijkstra
一、心路历程 这一个题目写了三天,可以说是非常挣扎了,明明是例题,但是就是倔强着不去看书上的题解,WA了7次,TLE了4次。 写了不知道多少条测试用例,一遍一遍的过,一点一点的调试。 最后终于找到…...
数据库管理员知识图谱
初入职场的程序猿,需要为自己做好职业规划,在职场的赛道上,需要保持学习,并不断点亮自己的技能树。 成为一名DBA需要掌握什么技能呢,先让Chat-GPT为我们回答一下: 数据库管理系统 (DBMS)知识ÿ…...
中兴服务器支持百度“文心一言”,助力AI产业发展
前段时间,中兴和百度正式对外宣布中兴服务器将会支持百度“文心一言”,为其提供更加强劲的算力支撑,从而加速“文心一言”的完事升级与更新迭代,助力AI产业化应用和生态的繁荣发展。 “文心一言”是百度基于文心大模型技术推出…...
STM 如何通过网络 time.windows.com获取时间
STM 如何通过网络 time.windows.com获取时间 在STM32中,你可以使用STM32Cube HAL库提供的网络套接字API来通过网络获取时间。以下是一个示例代码,演示如何通过time.windows.com获取时间: #include "stm32xxxx.h" #include "lwip/sockets.h" #include …...
数据结构——红黑树
文章目录 一.红黑树的定义二.红黑树的插入1.红黑树节点的定义2.红黑树的插入操作3.总结: 三.红黑树与AVL树的比较四.检验手写的红黑树五.源码 一.红黑树的定义 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色ÿ…...
【C++】数据结构与算法:常用排序算法
😏★,:.☆( ̄▽ ̄)/$:.★ 😏 这篇文章主要介绍常用排序算法。 学其所用,用其所学。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下,下次更新不迷路…...
【C++】Bullet3代码存档
之前试了一下Bullet3物理引擎,但在linux上编译失败,于是放弃了。令我不满的还有另外一个原因,下载的发行包竟然有500M。C的Bullet3代码根本用不了,大部分教程实际都是用的老版本。而且此项目还整了python版本,各种蹭人…...
弘扬“两弹一星”精神,勇攀科学技术高峰——道本科技商业大学党日活动圆满落幕
2023年8月2日,道本科技与商业大学携手举办了一场主题为“弘扬‘两弹一星’精神,勇攀科学技术高峰”的党日活动。本次活动旨在了解党领导下的中国核工业发展历程,传承和弘扬“两弹一星”精神,同时展示道本科技创新产品,…...
Java中创建对象的几种方式
背景 面试的时候有些面试官喜欢问这些, 这里简单记录一下. 常见方式 方式1: new XXXX(); 使用new关键字:这是最常见的创建对象的方式,使用new关键字后面跟上类名和参数列表(如果有),可以调用类的构造方法来创建对象…...
Python(三)
诚信像一面镜子,一旦打破,你的人格就会出现裂痕。 存在短路的情景 谢谢观看 Python(三)...
android 如何分析应用的内存(十五)——Visual Studio Code 调试Android应用
android 如何分析应用的内存(十五)——Visual Studio Code 调试Android 应用 在上一篇文章介绍了jdb调试java应用 接下来介绍用UI界面调试java应用,达到同jdb一样的效果。 同样的UI界面有很多选择,如Eclipse,Android …...
宁波银行最新内推码 MK4913
宁波银行最新内推码 MK4913 内推码: MK4913 内推二维码 : 网申路径: 网页端:登录宁波银行招聘官网: https://zhaopin.nbcb.com.cn 选择【校园招聘】-【招聘岗位】手机端:关注【宁波银行招聘】公众号&a…...
postgresql|数据库|MySQL数据库向postgresql数据库迁移的工具pgloader的部署和初步使用
前言: MySQL数据库和postgresql数据库之间的差异并不多,这里的差异指的是对SQL语言的支持两者并不大,但底层的东西差异是非常多的,例如,MySQL的innodb引擎概念,数据库用户管理,这些和postgresq…...
【Python从小白到高手】---函数基础
个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【Python小白从入门到精通】🎈 本专栏旨在分享学习Python的一点学习心得,欢迎大家在评论区讨论💌 目录…...
postman----传参格式(json格式、表单格式)
本文主要讲解postman使用post请求方法的2中传参方式:json格式、表单格式 首先了解下,postman进行接口测试,必须条件是: ♥请求地址 ♥请求协议 ♥请求方式 ♥请求头 ♥参数 json格式 先看一下接口文档,根据接口文档&…...
Uni-Dock:GPU 分子对接使用教程
github文件下载: git clone https://github.com/dptech-corp/Uni-Dock.git cd Uni-Dock/example/screening_test wget https://github.com/dptech-corp/Uni-Dock/releases/download/1.0.0/unidock 将此文件加入到全局变量中 chmod x unidock sudo mv unidock /…...
【Python】数据分析+数据挖掘——掌握Python和Pandas中的单元格替换操作
1. 前言 数据处理和清洗是数据分析和机器学习中至关重要的步骤。在数据处理过程中,我们经常需要对数据集进行清洗和转换,其中单元格替换是一个常用的技术。Python作为一种功能强大且灵活的编程语言,为数据处理提供了丰富的工具和库。Pandas库…...
Godot 4 源码分析 - 增加格式化字符串功能
Godot 4的主要字符串类型为String,已经设计得比较完善了,但有一个问题,格式化这块没怎么考虑。 String中有一个format函数,但这个函数只有两个参数,这咋用? String String::format(const Variant &va…...
C#中XML文档与Treeview控件操作的数据同步
在前文《C#使用XML和Treeview结合实现复杂数据采集功能》中,使用Treeview展示了XML的数据,问题是如果在Treeview上进行了操作,怎样同步更改XML数据的内容呢? 这个问题看似简单,实现起来有一点小麻烦。 要实现的操作功能…...
【Java Web基础】mvn命令、Maven的安装与配置
本文极大程度上来自Maven安装(超详解),但是担心安的过程中遇到什么不一样的问题,顺便加深印象,所以还是打算自己弄一篇。 目录 第一步:Download Maven第二步:解压与安装2.1 解压2.2 安装 第一步:Download …...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
Win系统权限提升篇UAC绕过DLL劫持未引号路径可控服务全检项目
应用场景: 1、常规某个机器被钓鱼后门攻击后,我们需要做更高权限操作或权限维持等。 2、内网域中某个机器被钓鱼后门攻击后,我们需要对后续内网域做安全测试。 #Win10&11-BypassUAC自动提权-MSF&UACME 为了远程执行目标的exe或者b…...
spring boot使用HttpServletResponse实现sse后端流式输出消息
1.以前只是看过SSE的相关文章,没有具体实践,这次接入AI大模型使用到了流式输出,涉及到给前端流式返回,所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...
