bzoj 1003: [ZJOI2006]物流运输（luogu 1772）-程序员宅基地

简述题意：

Description

物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。

Input

第一行是四个整数n（1<=n<=100）、m（1<=m<=20）、K和e。n表示货物运输所需天数，m表示码头总数，K表示每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度（>0）。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来一行是一个整数d，后面的d行每行是三个整数P（ 1 < P < m）、a、b（1 < = a < = b < = n）。表示编号为P的码头从第a天到第b天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一条从码头A到码头B的运输路线。

Output

包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。

Sample Input

5 5 10 81 2 11 3 31 4 22 3 22 4 43 4 13 5 24 5 242 2 33 1 13 3 34 4 5

Sample Output

HINT

前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)*3+(3+2)*2+10=32

算法：SPFA+DP

难度：NOIP

题解：

先预处理（O（ $n^2$ ））出从第i天到第j天走同一条路的最小花费 $f[i][j]$ ，

之后用 $dp[i]$ 表示前i天的最小花费，则 $dp[i]=min(dp[j]+f[j+1][i]*(i-j)+k)$

注意一些限制的细节就好，细节不少！

注意：数组要开大！题目描述没有给出边的数据范围，那么若图是完全图+双向边，则至多2000多条边！

不开大数组，TLE+RE！！！

更新dp时，注意不更新的判定！

本文链接：https://blog.csdn.net/qq_42369449/article/details/83348931

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

java privatekey输出字符串,从本地Java中的私钥字符串派生EC公钥以获取曲线secp256k1...-程序员宅基地

文章浏览阅读1.5k次。I need to derive an EC Public Key from an EC private key string without the "help" of any third party library.The Private key is externally produced and provided and I need to get the Public Key to ge..._ecnamedcurveparameterspec privatekey

c++11 之右值引用、移动语义、std::move_std move使用场景-程序员宅基地

文章浏览阅读335次。c++11引入了右值引用和移动语义（移动构造和移动赋值运算符），可以避免无谓的复制，提高程序性能。1.右值引用右值引用，记为T&&。左值是指表达式结束后依然存在的持久对象，右值是指表达式结束就不存在的临时对象。一个区分左值与右值的便捷方法是对表达式取地址，如果能则是左值，否则是右值。右值包括：非引用返回的临时变量、运算表达式产生的临时变量、字面值、lambda表达式、std::mo..._std move使用场景

智能车学习（十八）——电机学习-程序员宅基地

文章浏览阅读1k次。一、C车电机选择 1、摘要：因为C车模在四轮车的优势是有两个电机，可以进行主动差速，劣势是电机太弱了。。。。所以如何选择电机，就是个钱的问题了，电机多一点，就比较好选，但是C车电机跑多了就会变的很弱很弱。所以请准备好钞票。 2、选择方法：（1）使用恒流源，配合单片机程序，测试出，对应电压的电流和转速，一般采样10个点即可，正反转都要（2）使用Matlab进..._差速车电机选型csdn

python-can对Vector CAN FD（no-iso）的支持_python-can vector-程序员宅基地

文章浏览阅读4k次。CAN-FD首先由博世提出，早期的CAN-FD称之为“no-iso”；后来can-fd标准化（11898-2:2015），一个3位填充位计数器和一个额外的奇偶校验位被引入，CRC的计算值也改变了，导致两者不兼容。早期的CAN－FD控制器是“no-iso”的，而目前大部分CAN设备默认都是ISO的，在使用的时候需要选配。PCAN的硬件可以自动转换ISO和非ISO，但是Vector的必须要选，在没有CANoe等设备的时候，需要编程实现。Vector提供的最新驱动（≥10.x.x）可以做到这一点，以前的只能分别_python-can vector

Linux软件安装及管理程序（包含RPM管理工具、yum软件包管理器和源代码编译安装）#编译安装未全_linux茄子的安装包-程序员宅基地

文章浏览阅读111次。目录应用程序与系统命令的关系典型应用程序的目录结构常见的软件包封装类型RPM包管理工具RPM封装的软件包的命名格式rpm命令的格式查询已经安装的RPM软件信息查询文件或目录是由哪个RPM包生成的查询未安装的RPM包文件安装、升级、卸载RPM包安装与卸载lynx软件包（lynx命令是纯文本模式的网页浏览器）解决软件包依赖关系维护RPM数据库yum概述与常用命令四、源代码编译安装应用程序与系统命令的关系角色系统命令应用程序文件位置一般在/bin和/sbin目录中，或为Shell内部指_linux茄子的安装包

外排序（最小输者树实现）-程序员宅基地

文章浏览阅读7.3k次，点赞27次，收藏123次。问题描述应用竞赛树结构模拟实现外排序。基本要求（1）设计实现最小输者树结构ADT，ADT中应包括初始化、返回赢者，重构等基本操作。（2）设计实现外排序，外部排序中的生成最初归并串以及K路归并都应用最小输者树结构实现；（3）随机创建一个较长的文件；设计归并路数以及缓冲区的大小；获得外排序的访问磁盘的次数并进行分析。可采用小文件来模拟磁盘块。解题输者树介绍对于输者树的构建过程，数..._最小输者树