当前位置: 首页 > 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 …...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...