最短路 - Page 3

NOI2010海拔
DescriptionYT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单起见，可以将YT市看作一个正方形，每一个区域也可看作一个正方形。从而，YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路（简称道路），每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n=2)，城市被划分为2×2个区域，包括3×3个交叉路口和12条双向道路。小Z作为该市的市长，他根据统计信息得到...
02014年12月17日3,936最小割,STL,dijkstra

「BZOJ4016」[FJOI2014] 最短路径树问题
cxjyxx_me:先求一个最短路图然后再这个图上dfs对于一个点的所有出点按编号从小到大dfs这样可以保证dfs树就是题目要求的树然后在这棵树上跑树分治f[i][j][2]表示前i棵子树从根出发链长为j[0：最长长度][1:这个长度条件下的方案数]对于第i+1棵子树单独跑一个f’[i][j][2]意义一样枚举这颗子树上链长和f一起更新答案然后用f‘更新f[crayon-67680509db7ba395721307/] ...
52014年12月15日7,928STL,dijkstra,点分治
「BZOJ1027」[JSOI2007] 合金
Description某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。Input第一行两个...
82014年12月9日6,568floyd,几何
「BZOJ2407」探险
Description探险家小T好高兴！X国要举办一次溶洞探险比赛，获奖者将得到丰厚奖品哦！小T虽然对奖品不感兴趣，但是这个大振名声的机会当然不能错过！比赛即将开始，工作人员说明了这次比赛的规则：每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路，也有可能没有，但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发，并再次回到这个大溶洞。如果就这么点限制，那么问题就太简单了，可是举办方又...
12014年11月27日5,055STL,dijkstra
「BZOJ2259」[Oibh] 新型计算机
DescriptionTim正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数——自然数包括0），计算机先读取第一个数字S1，然后顺序向后读入S1个数字。接着再读一个数字S2，顺序向后读入S2个数字……依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处...
02014年11月25日4,575STL,dijkstra
「NOIP模拟赛」长途旅行
「题目描述」JY是一个爱旅游的探险家，也是一名强迫症患者。现在JY想要在C国进行一次长途旅行，C国拥有n个城市(编号为0,1,2...,n-1)，城市之间有m条道路，可能某个城市到自己有一条道路，也有可能两个城市之间有多条道路，通过每条道路都要花费一些时间。JY从0号城市开始出发，目的地为n–1号城市。由于JY想要好好参观一下C国，所以JY想要旅行恰好T小时。为了让自己的旅行更有意思，JY决定不在任何一个时刻停留(走...
42014年11月3日5,515spfa
「BZOJ1665」[Usaco2006 Open] The Climbing Wall 攀岩
DescriptionOneofthemostpopularattractionsatthecountyfairistheclimbingwall.Bessiewantstoplanhertripupthewallinadvanceandneedsyourhelp.Thewallis30,000millimeterswideandH(1001<=H<=30,000)millimetershighandhasF(1<=F<=10,000)hoof-holdsatuniqueX,Ycoordinatesexpressedinmillimeters.0,0isatthegroundlevelontheleftsideofthewall.Hoof-holdsareseparatedbyatleast300millimeterssincenocowcan...
02014年10月29日3,994STL,dijkstra
「NOIP模拟赛」花园的守护之神
题目描述看着正在被上古神兽们摧残的花园，花园的守护之神――小Bug同学泪流满面。然而，FZOI不相信眼泪，小bug与神兽们的战争将进行到底！通过google，小Bug得知，神兽们来自遥远的戈壁。为了扭转战局，小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂，由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie，而且可以...
32014年10月28日4,465最小割,STL,dijkstra
「NOIP模拟赛」小奇回地球
原题目名：时间与空间之旅2015.9.13日hzwer重制了题面与数据「题目背景」开学了，小奇在回地球的路上，遇到了一个棘手的问题。「问题描述」简单来说，它要从标号为1的星球到标号为n的星球，某一些星球之间有航线。由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球a到b耗费的时间和星球b到a耗费的时间不一定相同。宇宙法规定：“禁止在出发时间前到达目的地。”每艘飞船上都有速度调节装置，...
32014年10月28日5,427spfa,二分法
「BZOJ2709」[Violet 1] 迷宫花园
DescriptionInputOutputSampleInput22.545######S##E######211312#############S###E#####################################################################SampleOutput0.500000.21053HINTSource题解。。。。二分+最短路判定即可不知道为何读入会出现奇怪的问题让我re了一版。。。。一直检查数组。。。[crayon-6768050a01850893465313/] ...
02014年10月27日4,046STL,dijkstra,二分法
「BZOJ2143」飞飞侠
Description飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵，每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么，任何飞飞侠都只需要在(i,j)支付Aij的费用...
22014年10月23日6,556STL,dijkstra
「BZOJ1097」[POI2007] 旅游景点atr
DescriptionFGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅行的距离尽量短，这样他就有足...
02014年10月19日5,461dijkstra,状压动规