• 【bzoj2709】[Violet 1]迷宫花园

    【bzoj2709】[Violet 1]迷宫花园

    DescriptionInputOutputSampleInput22.545######S##E######211312#############S###E#####################################################################SampleOutput0.500000.21053HINTSource题解。。。。二分+最短路判定即可不知道为何读入会出现奇怪的问题让我re了一版。。。。一直检查数组。。。[crayon-58824f9f6575c119802602/] ...

    02014年10月27日1,220STL,dijkstra,二分法
  • 【bzoj2143】飞飞侠

    【bzoj2143】飞飞侠

    Description飞飞国是一个传说中的国度,国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵,每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么,任何飞飞侠都只需要在(i,j)支付Aij的费用...

    02014年10月23日1,736STL,dijkstra
  • 【bzoj1097】[POI2007]旅游景点atr

    【bzoj1097】[POI2007]旅游景点atr

    DescriptionFGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的,比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山,而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的,他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸,他希望在满足他的要求的情况下,旅行的距离尽量短,这样他就有足...

    02014年10月19日1,760dijkstra,状压动规
  • 【codecomb2090】最小乘积路

    【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日893dijkstra
  • 【bzoj3389】[Usaco2004 Dec]Cleaning Shifts安排值班

    【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日1,039dijkstra
  • 【bzoj3402】[Usaco2009 Open]Hide and Seek 捉迷藏

    【bzoj3402】[Usaco2009 Open]Hide and Seek 捉迷藏

    Description    贝茜在和约翰玩一个“捉迷藏”的游戏.    她正要找出所有适合她躲藏的安全牛棚.一共有N(2≤N≤20000)个牛棚,被编为1到N号.她知道约翰(捉牛者)从牛棚1出发.所有的牛棚由M(1≤M≤50000)条双向路连接,每条双向路连接两个不同的牛棚.所有的牛棚都是相通的.贝茜认为同牛棚1距离最远的的牛棚是安全的.两个牛棚间的距离是指,从一个牛棚到另一个牛棚最少需要通过的道路数量.请帮贝茜找出所有的安...

    02014年9月26日919dijkstra
  • 【bzoj1598】[Usaco2008 Mar]牛跑步

    【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日1,424dijkstra
  • 【bzoj1752】[Usaco2005 qua]Til the Cows Come Home

    【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日929dijkstra
  • 【bzoj2662】[BeiJing wc2012]冻结

    【bzoj2662】[BeiJing wc2012]冻结

    Description “我要成为魔法少女!”“那么,以灵魂为代价,你希望得到什么?”“我要将有关魔法和奇迹的一切,封印于卡片之中„„”在这个愿望被实现以后的世界里,人们享受着魔法卡片(SpellCard,又名符卡)带来的便捷。现在,不需要立下契约也可以使用魔法了!你还不来试一试?比如,我们在魔法百科全书(Encyclopedia of Spells)里用“freeze”作为关键字来查询,会有很多有趣的结果。例如,我们熟知的Cirno,她的冰...

    02014年8月13日1,332dijkstra
  • 【bzoj3040】最短路(road)

    【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条边采用读入方式:...

    02014年8月13日2,355dijkstra
  • 【bzoj2346】[Baltic 2011]Lamp

    【bzoj2346】[Baltic 2011]Lamp

    Description2255是一个傻X,他连自己家灯不亮了都不知道。某天TZ大神路过他家,发现了这一情况,于是TZ开始行侠仗义了。TZ发现是电路板的问题,他打开了电路板,发现线路根本没有连上!!于是他强大的脑力可以使某个格子上的线路从\变为/,或者从/变为\。2255不会电路(因为他什么都不会),但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。如果无法变亮,输出“NOSOLUTION”。n,m<=500SampleInput...

    02014年8月5日1,042dijkstra
  • 【bzoj2304】[APIO2011]寻路path

    【bzoj2304】[APIO2011]寻路path

    DescriptionTooDee是一块二维格子状的土地(就像著名的笛卡尔坐标系那样),在这里生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物,它们只在二维活动,而且它们非常的文明开化。TooDee的蜂窝和正常世界的蜂窝也是很不一样的,它们是矩形的且它们的边平行于TooDee的地理坐标系,就是说矩形的边或者是东西走向,或者是南北走向。因为Dees是很高级的生物,它们有很多固定的飞行轨道,这些轨道由一些平行于坐标轴的线段组成,...

    12014年8月5日2,031模拟,spfa,dijkstra,线段树
  • 【bzoj1674】[Usaco2005]Part Acquisition

    【bzoj1674】[Usaco2005]Part Acquisition

    DescriptionThecowshavebeensentonamissionthroughspacetoacquireanewmilkingmachinefortheirbarn.TheyareflyingthroughaclusterofstarscontainingN(1<=N<=50,000)planets,eachwithatradingpost.ThecowshavedeterminedwhichofK(1<=K<=1,000)typesofobjects(numbered1..K)eachplanetintheclusterdesires,andwhichproductstheyhavetotrade.Noplanethasdevelopedcurrency,sotheyworkunderthebartersystem:alltr...

    02014年8月2日858dijkstra