• 「NOIP模拟赛」花园的守护之神

    「NOIP模拟赛」花园的守护之神

    题目描述看着正在被上古神兽们摧残的花园,花园的守护之神――小Bug同学泪流满面。然而,FZOI不相信眼泪,小bug与神兽们的战争将进行到底!通过google,小Bug得知,神兽们来自遥远的戈壁。为了扭转战局,小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂,由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie,而且可以...

    32014年10月28日2,049最小割,STL,dijkstra
  • 「BZOJ2709」[Violet 1] 迷宫花园

    「BZOJ2709」[Violet 1] 迷宫花园

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

    02014年10月27日2,097STL,dijkstra,二分法
  • 「BZOJ2143」飞飞侠

    「BZOJ2143」飞飞侠

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

    02014年10月23日3,013STL,dijkstra
  • 「BZOJ1097」[POI2007] 旅游景点atr

    「BZOJ1097」[POI2007] 旅游景点atr

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

    02014年10月19日3,236dijkstra,状压动规
  • 「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日1,523dijkstra
  • 「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,745dijkstra
  • 「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日1,559dijkstra
  • 「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日2,630dijkstra
  • 「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日1,545dijkstra
  • 「BZOJ2662」[BJ WC2012] 冻结

    「BZOJ2662」[BJ WC2012] 冻结

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

    12014年8月13日2,316dijkstra
  • 「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条边采用读入方式:...

    22014年8月13日4,528dijkstra
  • 「BZOJ2346」[Baltic 2011] Lamp

    「BZOJ2346」[Baltic 2011] Lamp

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

    02014年8月5日1,711dijkstra