dijkstra - Page 2 - hzwer.com

「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,932STL,dijkstra

「NOIP模拟赛」花园的守护之神
题目描述看着正在被上古神兽们摧残的花园，花园的守护之神――小Bug同学泪流满面。然而，FZOI不相信眼泪，小bug与神兽们的战争将进行到底！通过google，小Bug得知，神兽们来自遥远的戈壁。为了扭转战局，小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂，由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie，而且可以...
32014年10月28日4,402STL,最小割,dijkstra
「BZOJ2709」[Violet 1] 迷宫花园
DescriptionInputOutputSampleInput22.545######S##E######211312#############S###E#####################################################################SampleOutput0.500000.21053HINTSource题解。。。。二分+最短路判定即可不知道为何读入会出现奇怪的问题让我re了一版。。。。一直检查数组。。。[crayon-674412cb638d7552713279/] ...
02014年10月27日3,971STL,dijkstra,二分法
「BZOJ2143」飞飞侠
Description飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵，每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么，任何飞飞侠都只需要在(i,j)支付Aij的费用...
22014年10月23日6,468STL,dijkstra
「BZOJ1097」[POI2007] 旅游景点atr
DescriptionFGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅行的距离尽量短，这样他就有足...
02014年10月19日5,402dijkstra,状压动规
「codecomb2090」最小乘积路
题目描述给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。输入格式第一行读入两个整数n，m，表示共n个点m条边。接下来m行，每行三个正整数x，y，z，表示点x到点y有一条边权为z的边。输出格式输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此输出它模9987的余数即可。样例数据1输入331232331310输出9备注对于20%的数据，n<=10。对于100%的数据，n<=1000，m<=1000000。边权不超过10000。题...
02014年10月13日3,496dijkstra
「BZOJ3389」[Usaco2004 Dec] Cleaning Shifts安排值班
Description 一天有T(1≤T≤10^6)个时段．约翰正打算安排他的N(1≤N≤25000)只奶牛来值班，打扫打扫牛棚卫生．每只奶牛都有自己的空闲时间段[Si，Ei](1≤Si≤Ei≤T)，只能把空闲的奶牛安排出来值班．而且，每个时间段必需有奶牛在值班．那么，最少需要动用多少奶牛参与值班呢？如果没有办法安排出合理的方案，就输出-1.Input 第1行：N，T．第2到N+1行：Si，Ei．Output 最少安排...
32014年10月1日3,383dijkstra
「BZOJ3402」[Usaco2009 Open] Hide and Seek 捉迷藏
Description 贝茜在和约翰玩一个“捉迷藏”的游戏．她正要找出所有适合她躲藏的安全牛棚．一共有N(2≤N≤20000)个牛棚，被编为1到N号．她知道约翰（捉牛者）从牛棚1出发．所有的牛棚由M(1≤M≤50000)条双向路连接，每条双向路连接两个不同的牛棚．所有的牛棚都是相通的．贝茜认为同牛棚1距离最远的的牛棚是安全的．两个牛棚间的距离是指，从一个牛棚到另一个牛棚最少需要通过的道路数量．请帮贝茜找出所有的安...
02014年9月26日3,422dijkstra
「BZOJ1598」[Usaco2008 Mar] 牛跑步
DescriptionBESSIE准备用从牛棚跑到池塘的方法来锻炼.但是因为她懒,她只准备沿着下坡的路跑到池塘,然后走回牛棚.BESSIE也不想跑得太远,所以她想走最短的路经.农场上一共有M(1<=M<=10,000)条路,每条路连接两个用1..N(1<=N<=1000)标号的地点.更方便的是,如果X>Y,则地点X的高度大于地点Y的高度.地点N是BESSIE的牛棚;地点1是池塘.很快,BESSIE厌倦了一直走同一条路.所以她想走不同的路...
02014年9月3日5,634dijkstra
「BZOJ1752」[Usaco2005 qua] Til the Cows Come Home
DescriptionBessieisoutinthefieldandwantstogetbacktothebarntogetasmuchsleepaspossiblebeforeFarmerJohnwakesherforthemorningmilking.Bessieneedsherbeautysleep,soshewantstogetbackasquicklyaspossible.FarmerJohn'sfieldhasN(2<=N<=1000)landmarksinit,uniquelynumbered1..N.Landmark1isthebarn;theappletreegroveinwhichBessiestandsalldayislandmarkN.CowstravelinthefieldusingT(1<=T<=2000...
02014年8月27日3,482dijkstra
「BZOJ2662」[BJ WC2012] 冻结
Description “我要成为魔法少女！”“那么，以灵魂为代价，你希望得到什么？”“我要将有关魔法和奇迹的一切，封印于卡片之中„„”在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。现在，不需要立下契约也可以使用魔法了！你还不来试一试？比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。例如，我们熟知的Cirno，她的冰...
02014年8月13日4,641dijkstra
「BZOJ3040」最短路(road)
DescriptionN个点，M条边的有向图，求点1到点N的最短路（保证存在）。1<=N<=1000000，1<=M<=10000000Input第一行两个整数N、M，表示点数和边数。第二行六个整数T、rxa、rxc、rya、ryc、rp。前T条边采用如下方式生成：1.初始化x=y=z=0。2.重复以下过程T次：x=(x*rxa+rxc)%rp;y=(y*rya+ryc)%rp;a=min(x%n+1,y%n+1);b=max(y%n+1,y%n+1);则有一条从a到b的，长度为1e8-100*a的有向边。后M-T条边采用读入方式：...
12014年8月13日7,819dijkstra