• 【NOIP模拟赛】长途旅行

    【NOIP模拟赛】长途旅行

    【题目描述】JY是一个爱旅游的探险家,也是一名强迫症患者。现在JY想要在C国进行一次长途旅行,C国拥有n个城市(编号为0,1,2...,n-1),城市之间有m条道路,可能某个城市到自己有一条道路,也有可能两个城市之间有多条道路,通过每条道路都要花费一些时间。JY从0号城市开始出发,目的地为n–1号城市。由于JY想要好好参观一下C国,所以JY想要旅行恰好T小时。为了让自己的旅行更有意思,JY决定不在任何一个时刻停留(走...

    32014年11月3日2,153spfa
  • 【bzoj1665】[Usaco2006 Open]The Climbing Wall 攀岩

    【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日1,596STL,dijkstra
  • 【NOIP模拟赛】花园的守护之神

    【NOIP模拟赛】花园的守护之神

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

    32014年10月28日1,589STL,最小割,dijkstra
  • 【NOIP模拟赛】小奇回地球

    【NOIP模拟赛】小奇回地球

    原题目名:时间与空间之旅2015.9.13日hzwer重制了题面与数据【题目背景】开学了,小奇在回地球的路上,遇到了一个棘手的问题。 【问题描述】简单来说,它要从标号为1的星球到标号为n的星球,某一些星球之间有航线。由于超时空隧道的存在,从一个星球到另一个星球时间可能会倒流,而且,从星球a到b耗费的时间和星球b到a耗费的时间不一定相同。 宇宙法规定:“禁止在出发时间前到达目的地。”每艘飞船上都有速度调节装置,...

    32014年10月28日1,741spfa,二分法
  • 【bzoj2709】[Violet 1]迷宫花园

    【bzoj2709】[Violet 1]迷宫花园

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

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

    【bzoj2143】飞飞侠

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

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

    【bzoj1097】[POI2007]旅游景点atr

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

    02014年10月19日2,569dijkstra,状压动规
  • 【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,277dijkstra
  • 【bzoj2324】[ZJOI2011]营救皮卡丘

    【bzoj2324】[ZJOI2011]营救皮卡丘

    Description皮卡丘被火箭队用邪恶的计谋抢走了!这三个坏家伙还给小智留下了赤果果的挑衅!为了皮卡丘,也为了正义,小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点,据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发,营救被困在N号据点的皮卡丘。为了方便起见,我们将真新镇视为0号据点,一开始K个人都在0号点。由于火箭队的重重布防,要想摧毁K号据点,必须按照顺序先摧...

    02014年10月9日3,063费用流,floyd
  • 【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,435dijkstra
  • 【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,285dijkstra
  • 【poj1734】Sightseeing trip

    【poj1734】Sightseeing trip

    DescriptionThereisatravelagencyinAdeltontownonZanzibarisland.Ithasdecidedtoofferitsclients,besidesmanyotherattractions,sightseeingthetown.Toearnasmuchaspossiblefromthisattraction,theagencyhasacceptedashrewddecision:itisnecessarytofindtheshortestroutewhichbeginsandendsatthesameplace.Yourtaskistowriteaprogramwhichfindssucharoute.InthetownthereareNcrossingpointsnumberedfrom1toNandMtwo-wayr...

    02014年9月24日1,340floyd
  • 【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,139dijkstra