标签 - 最短路

? 解题记录 ? ? 洛谷 ? ? 最短路 ?    2018-11-13 09:12:52    403    0    0
题目描述小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面, 华容道是否根本就无法完成,如果能完成, 最少需要多少时间。 小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的: 在一个 n×m 棋盘上有n×m个格子,其中有且只有一个格子是空白的,其余n×m−1个格子上每个格子上有一个棋子,每个棋子的大小都是 1×1 的; 有些棋子是固定的,有些棋子则是可以移动的; 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。 游戏的目的是把某个指定位置可以
? 解题记录 ? ? 洛谷 ? ? 最短路 ? ? 动态规划 ?    2018-10-09 08:25:53    417    0    0
策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图,且没有自环和重边。其中 1 号点是公园的入口, N 号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间。 策策每天都会去逛公园,他总是从 1 号点进去,从 N 号点出来。 策策喜欢新鲜的事物,他不希望有两天逛公园的路线完全一样,同时策策还是一个特别热爱学习的好孩子,他不希望每天在逛公园这件事上花费太多的时间。如果 1 号点到 N 号点的最短路
? 解题记录 ? ? 洛谷 ? ? 最短路 ? ? 状态压缩 ?    2018-10-06 17:42:59    622    0    0
题解 for C:逃亡 首先我们看看这道题的部分分: 对于30%" role="presentation" style="position: relative;">30%30%30\%的数据,我们写个爆搜搜过去就可以了。 对于60%" role="presentation" style="position: relative;">60%60%60\%的数据,注意到n,m" role="presentation" style="position: relative;">n,mn,mn,m为100" role="present
? 解题记录 ? ? 洛谷 ? ? 分块 ? ? 最短路 ?    2018-07-15 11:07:54    803    1    0
印尼首都雅加达市有 N" data-mce-tabindex="0">N 座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为 0" data-mce-tabindex="0">0 到 N−1" data-mce-tabindex="0">N−1。除了这 N" data-mce-tabindex="0">N 座摩天楼外,雅加达市没有其他摩天楼。 有 M" data-mce-tabindex="0">M 只叫做 “doge” 的神秘生物在雅加达市居住
? 解题记录 ? ? 洛谷 ? ? AC自动机 ? ? 矩阵快速幂 ? ? 最短路 ?    2018-06-27 22:01:21    559    0    0
题目描述  给出n个互不包含的字符串,要求你求出一个最短的字符串S,使得这n个字符串在S中总共至少出现m次,问S最短是多少   (, ), 总字符不超过  。  输入格式: 第一行两个整数n, m 接下来n行n个字符串 输出格式:  一行表示最短长度。   输入输出样例输入样例#1: 复制4 5 monika tomek szymon bernard 输出样例#1: 复制23​  ​  这题好想,就是处理每一个字符串AC自动机结尾到另一个结尾的最短路矩阵
? 解题记录 ? ? 洛谷 ? ? 拓扑排序 ? ? 最短路 ?    2017-11-25 14:34:13    613    0    0
题目描述最近,Elaxia和w的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们 必须合理地安排两个人在一起的时间。Elaxia和w每天都要奔波于宿舍和实验室之间,他们 希望在节约时间的前提下,一起走的时间尽可能的长。 现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图:地图上有N个路 口,M条路,经过每条路都需要一定的时间。 具体地说,就是要求无向图中,两对点间最短路的最长公共路径。 输入输出格式输入格式:   第一行:两个整数N和M(含义如题目描述)。 第二行:四个整数x1、y1、x2、y2(1 ≤ x1 ≤ N,1 ≤ y1 ≤ N,1 ≤ x2
? 解题记录 ? ? 动态规划 ? ? 最短路 ? ? 洛谷 ?    2017-11-05 12:14:39    328    0    0
题目描述物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在,有的时候某个码头会无法装卸货物。这时候就必须修改运输路线,让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情,会带来额外的成本。因此物流公司希望能够订一个n天的运输计划,使得总成本尽可能地小。 输入输出格式输入格式:   第一行是四个整数n(l≤n≤100)、m(l≤m≤20)、K和e。n表示货物运输所需天数,m表示码头总数,K表示每次修改运输路线所需成本,e表
? 解题记录 ? ? BZOJ ? ? 最短路 ?    2017-10-20 16:29:35    448    0    0
2118: 墨墨的等式Time Limit: 10 Sec  Memory Limit: 259 MBSubmit: 2271  Solved: 893[Submit][Status][Discuss]Description墨墨突然对等式很感兴趣,他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件,他要求你编写一个程序,给定N、{an}、以及B的取值范围,求出有多少B可以使等式存在非负整数解。 Input输入的第一行包含3个正整数,分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上
? 解题记录 ? ? POJ ? ? 补档计划第一期 ? ? 最短路 ?    2017-10-01 10:17:30    364    0    0
Wormholes Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 55119 Accepted: 20556 Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to
? 解题记录 ? ? 洛谷 ? ? 最短路 ?    2017-07-27 10:00:56    411    0    0
题目描述The good folks in Texas are having a heatwave this summer. Their Texas Longhorn cows make for good eating but are not so adept at creating creamy delicious dairy products. Farmer John is leading the charge to deliver plenty of ice cold nutritious milk to Texas so the Texans will not suffer the h