当前位置: 首页 > news >正文

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

一、心路历程 这一个题目写了三天&#xff0c;可以说是非常挣扎了&#xff0c;明明是例题&#xff0c;但是就是倔强着不去看书上的题解&#xff0c;WA了7次&#xff0c;TLE了4次。 写了不知道多少条测试用例&#xff0c;一遍一遍的过&#xff0c;一点一点的调试。 最后终于找到…...

数据库管理员知识图谱

初入职场的程序猿&#xff0c;需要为自己做好职业规划&#xff0c;在职场的赛道上&#xff0c;需要保持学习&#xff0c;并不断点亮自己的技能树。  成为一名DBA需要掌握什么技能呢&#xff0c;先让Chat-GPT为我们回答一下&#xff1a; 数据库管理系统 (DBMS)知识&#xff…...

中兴服务器支持百度“文心一言”,助力AI产业发展

前段时间&#xff0c;中兴和百度正式对外宣布中兴服务器将会支持百度“文心一言”&#xff0c;为其提供更加强劲的算力支撑&#xff0c;从而加速“文心一言”的完事升级与更新迭代&#xff0c;助力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.总结&#xff1a; 三.红黑树与AVL树的比较四.检验手写的红黑树五.源码 一.红黑树的定义 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff…...

【C++】数据结构与算法:常用排序算法

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍常用排序算法。 学其所用&#xff0c;用其所学。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff0c;下次更新不迷路&#x1…...

【C++】Bullet3代码存档

之前试了一下Bullet3物理引擎&#xff0c;但在linux上编译失败&#xff0c;于是放弃了。令我不满的还有另外一个原因&#xff0c;下载的发行包竟然有500M。C的Bullet3代码根本用不了&#xff0c;大部分教程实际都是用的老版本。而且此项目还整了python版本&#xff0c;各种蹭人…...

弘扬“两弹一星”精神,勇攀科学技术高峰——道本科技商业大学党日活动圆满落幕

2023年8月2日&#xff0c;道本科技与商业大学携手举办了一场主题为“弘扬‘两弹一星’精神&#xff0c;勇攀科学技术高峰”的党日活动。本次活动旨在了解党领导下的中国核工业发展历程&#xff0c;传承和弘扬“两弹一星”精神&#xff0c;同时展示道本科技创新产品&#xff0c;…...

Java中创建对象的几种方式

背景 面试的时候有些面试官喜欢问这些, 这里简单记录一下. 常见方式 方式1: new XXXX(); 使用new关键字&#xff1a;这是最常见的创建对象的方式&#xff0c;使用new关键字后面跟上类名和参数列表&#xff08;如果有&#xff09;&#xff0c;可以调用类的构造方法来创建对象…...

Python(三)

诚信像一面镜子&#xff0c;一旦打破&#xff0c;你的人格就会出现裂痕。 存在短路的情景 谢谢观看 Python(三)...

android 如何分析应用的内存(十五)——Visual Studio Code 调试Android应用

android 如何分析应用的内存&#xff08;十五&#xff09;——Visual Studio Code 调试Android 应用 在上一篇文章介绍了jdb调试java应用 接下来介绍用UI界面调试java应用&#xff0c;达到同jdb一样的效果。 同样的UI界面有很多选择&#xff0c;如Eclipse&#xff0c;Android …...

宁波银行最新内推码 MK4913

宁波银行最新内推码 MK4913 内推码&#xff1a; MK4913 内推二维码 &#xff1a; 网申路径&#xff1a; 网页端&#xff1a;登录宁波银行招聘官网&#xff1a; https://zhaopin.nbcb.com.cn 选择【校园招聘】-【招聘岗位】手机端&#xff1a;关注【宁波银行招聘】公众号&a…...

postgresql|数据库|MySQL数据库向postgresql数据库迁移的工具pgloader的部署和初步使用

前言&#xff1a; MySQL数据库和postgresql数据库之间的差异并不多&#xff0c;这里的差异指的是对SQL语言的支持两者并不大&#xff0c;但底层的东西差异是非常多的&#xff0c;例如&#xff0c;MySQL的innodb引擎概念&#xff0c;数据库用户管理&#xff0c;这些和postgresq…...

【Python从小白到高手】---函数基础

个人主页&#xff1a;平行线也会相交 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 平行线也会相交 原创 收录于专栏【Python小白从入门到精通】&#x1f388; 本专栏旨在分享学习Python的一点学习心得&#xff0c;欢迎大家在评论区讨论&#x1f48c; 目录…...

postman----传参格式(json格式、表单格式)

本文主要讲解postman使用post请求方法的2中传参方式&#xff1a;json格式、表单格式 首先了解下&#xff0c;postman进行接口测试&#xff0c;必须条件是&#xff1a; ♥请求地址 ♥请求协议 ♥请求方式 ♥请求头 ♥参数 json格式 先看一下接口文档&#xff0c;根据接口文档&…...

Uni-Dock:GPU 分子对接使用教程

github文件下载&#xff1a; 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. 前言 数据处理和清洗是数据分析和机器学习中至关重要的步骤。在数据处理过程中&#xff0c;我们经常需要对数据集进行清洗和转换&#xff0c;其中单元格替换是一个常用的技术。Python作为一种功能强大且灵活的编程语言&#xff0c;为数据处理提供了丰富的工具和库。Pandas库…...

Godot 4 源码分析 - 增加格式化字符串功能

Godot 4的主要字符串类型为String&#xff0c;已经设计得比较完善了&#xff0c;但有一个问题&#xff0c;格式化这块没怎么考虑。 String中有一个format函数&#xff0c;但这个函数只有两个参数&#xff0c;这咋用&#xff1f; String String::format(const Variant &va…...

C#中XML文档与Treeview控件操作的数据同步

在前文《C#使用XML和Treeview结合实现复杂数据采集功能》中&#xff0c;使用Treeview展示了XML的数据&#xff0c;问题是如果在Treeview上进行了操作&#xff0c;怎样同步更改XML数据的内容呢&#xff1f; 这个问题看似简单&#xff0c;实现起来有一点小麻烦。 要实现的操作功能…...

【Java Web基础】mvn命令、Maven的安装与配置

本文极大程度上来自Maven安装(超详解)&#xff0c;但是担心安的过程中遇到什么不一样的问题&#xff0c;顺便加深印象&#xff0c;所以还是打算自己弄一篇。 目录 第一步&#xff1a;Download Maven第二步&#xff1a;解压与安装2.1 解压2.2 安装 第一步&#xff1a;Download …...

分子对接盒子参数智能生成:GetBox-PyMOL-Plugin蛋白质结构分析专业指南

分子对接盒子参数智能生成&#xff1a;GetBox-PyMOL-Plugin蛋白质结构分析专业指南 【免费下载链接】GetBox-PyMOL-Plugin A PyMOL Plugin for calculating docking box for LeDock, AutoDock and AutoDock Vina. 项目地址: https://gitcode.com/gh_mirrors/ge/GetBox-PyMOL-…...

别再只会让舵机转圈了!用Arduino和SG90实现精准角度控制的保姆级教程

从转圈到精准控制&#xff1a;Arduino与SG90舵机的高级应用指南 第一次接触舵机时&#xff0c;我们往往满足于让它简单地来回转动——这确实很有趣&#xff0c;就像给玩具注入了生命。但当你真正想用它构建一个机械臂、智能云台或是自动喂食器时&#xff0c;这种粗放的控制方式…...

别再只会用中断了!用状态机查表法搞定AB相编码器,STM32代码实测(附防抖技巧)

状态机查表法在AB相编码器中的工程实践与优化 记得第一次在电机控制项目中使用旋转编码器时&#xff0c;我整整花了三天时间调试中断服务程序。每当电机转速提高&#xff0c;计数器就会莫名其妙地漏脉冲或跳变。直到发现状态机查表法这个"神器"&#xff0c;才真正解决…...

霜儿-汉服-造相Z-Turbo作品集:看看AI能生成多美的汉服少女图

霜儿-汉服-造相Z-Turbo作品集&#xff1a;看看AI能生成多美的汉服少女图 1. 惊艳开篇&#xff1a;AI汉服艺术的魅力 当传统汉服遇上现代AI技术&#xff0c;会碰撞出怎样的火花&#xff1f;霜儿-汉服-造相Z-Turbo给出了令人惊叹的答案。这个基于Xinference部署的文生图模型服务…...

视频高清低延时直播/音视频点播/云点播/云直播EasyDSS在校园教育/K12教育等各场景中的应用介绍

在线教育的核心竞争力&#xff0c;归根结底在于教学体验的优劣&#xff0c;而视频技术作为线上教学的核心载体&#xff0c;直接决定了教学体验的上限。随着在线教育行业的快速迭代&#xff0c;学员对线上课堂的要求愈发严苛&#xff1a;不仅需要高清流畅、稳定无卡顿的音视频传…...

免费开源:如何用LiteDB.Studio高效管理嵌入式数据库?

免费开源&#xff1a;如何用LiteDB.Studio高效管理嵌入式数据库&#xff1f; 【免费下载链接】LiteDB.Studio A GUI tool for viewing and editing documents for LiteDB v5 项目地址: https://gitcode.com/gh_mirrors/li/LiteDB.Studio 在嵌入式数据库管理领域&#xf…...

ROS与Webots协同开发:舵轮底盘运动控制实战解析

1. 舵轮底盘的核心原理与结构设计 舵轮底盘作为全向移动机器人的核心部件&#xff0c;其独特之处在于每个轮子都具备独立转向和驱动的能力。这种设计使得机器人能够在平面内实现任意方向的平移和旋转&#xff0c;完全突破了传统差速底盘的运动限制。我曾在物流AGV项目中实测过&…...

告别重复劳动:用快马AI智能生成OpenCode风格的高效工具函数

最近在开发一个需要大量表单验证的项目时&#xff0c;我发现每次都要重复写类似的验证逻辑&#xff0c;既浪费时间又容易出错。于是我开始寻找更高效的解决方案&#xff0c;最终在InsCode(快马)平台上找到了理想的工具。 需求分析 表单验证是每个Web项目都绕不开的基础功能。常…...

PDFMathTranslate:突破语言障碍的学术文档翻译终极解决方案

PDFMathTranslate&#xff1a;突破语言障碍的学术文档翻译终极解决方案 【免费下载链接】PDFMathTranslate PDF scientific paper translation with preserved formats - 基于 AI 完整保留排版的 PDF 文档全文双语翻译&#xff0c;支持 Google/DeepL/Ollama/OpenAI 等服务&…...

新手入门指南:在快马平台用AI生成代码理解云桌面基础概念

今天想和大家分享一个特别适合新手理解云桌面基础概念的实践方法。作为一个刚接触云计算的小白&#xff0c;我最初对"一台主机创建多个云桌面"这个概念也是一头雾水&#xff0c;直到在InsCode(快马)平台上尝试用AI生成代码来模拟这个过程&#xff0c;才真正搞明白其中…...