最短路 - Page 5

「BZOJ2100」[Usaco2010 Dec] Apple Delivery
DescriptionBessiehastwocrispredapplestodelivertotwoofherfriendsintheherd.Ofcourse,shetravelstheC(1<=C<=200,000)cowpathswhicharearrangedastheusualgraphwhichconnectsP(1<=P<=100,000)pasturesconvenientlynumberedfrom1..P:nocowpathleadsfromapasturetoitself,cowpathsarebidirectional,eachcowpathhasanassociateddistance,and,bestofall,itisalwayspossibletogetfromanypasturetoanyotherpasture....
02014年7月29日4,480spfa

「BZOJ2015」[Usaco2010 Feb] Chocolate Giving
DescriptionFarmerJohn有B头奶牛(1<=B<=25000)，有N(2*B<=N<=50000)个农场，编号1-N，有M(N-1<=M<=100000)条双向边，第i条边连接农场R_i和S_i(1<=R_i<=N;1<=S_i<=N)，该边的长度是L_i(1<=L_i<=2000)。居住在农场P_i的奶牛A(1<=P_i<=N)，它想送一份新年礼物给居住在农场Q_i(1<=Q_i<=N)的奶牛B，但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物，...
02014年7月29日4,651spfa
「NOIP模拟赛」笨笨的电话网络
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1≤N≤1000)根据1…n顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有p(0≤p≤10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。第i对电线杆的两个端点分别是ai，bi，它们的距离为li(1≤li≤1000000)。数据中每对(ai，bi)只出现一次。编号为1的电话杆已经接入了全国的电...
02014年7月8日4,516spfa,二分法
「NOIP模拟赛」坑爹的GPS
坑爹的GPS（gpsduel.c/.cpp/.pas）有一天，FJ买了一辆车，但是，他一手下载了两个GPS系统。好了现在麻烦的事情来了，GPS有一个功能大概大家也知道，如果FJ没有按照GPS内置地图的最短路走，GPS就会报错来骚扰你。现在FJ准备从他的农舍（在1这个点）开车到他的谷屋（n这个点）。FJ给了你两个GPS系统内置地图的信息，他想知道，他最少会听到多少次报错（如果FJ走的路同时不满足两个GPS，报错次数+2）读...
22014年7月3日4,066最短路
「BZOJ1179」[Apio2009] 抢掠计划atm
DescriptionInput第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号Output输出一个...
02014年6月16日6,728spfa,图的连通
「BZOJ1715」[Usaco2006 Dec] Wormholes 虫洞
DescriptionJohn在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N（从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。John将向你提供F(1<=F<=5)个农场的地图。没有小路会...
02014年5月24日7,990spfa
「BZOJ1631」[Usaco2007 Feb] Cow Party
Description 农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？Input第1行:三个用空格隔开的整数.第2行到第M+1行,每行三个用空格隔开的整数:Ai,Bi,以及Ti.表示一条道路的起点,终...
22014年5月23日3,792spfa
「1612」[Usaco2008 Jan] Cow Contest奶牛的比赛
DescriptionFJ的N(1<=N<=100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1<=A<=N;1<=B<=N;A!=B)，那么她们的对决中，编号为A的奶牛总是能胜出。F...
02014年5月22日5,842floyd
「BZOJ1690」[Usaco2007 Dec] 奶牛的旅行
Description作为对奶牛们辛勤工作的回报，FarmerJohn决定带她们去附近的大城市玩一天。旅行的前夜，奶牛们在兴奋地讨论如何最好地享受这难得的闲暇。很幸运地，奶牛们找到了一张详细的城市地图，上面标注了城市中所有L(2<=L<=1000)座标志性建筑物（建筑物按1..L顺次编号），以及连接这些建筑物的P(2<=P<=5000)条道路。按照计划，那天早上FarmerJohn会开车将奶牛们送到某个她们指定的建筑物旁边，等奶牛们完成...
32014年5月19日5,634spfa
「NOIP模拟赛」虫洞
「题目描述」N个虫洞，M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。从白洞跃迁到黑洞，消耗的燃料值减少delta，若该条路径消耗的燃料值变为负数的话，取为0。从黑洞跃迁到白洞，消耗的燃料值增加delta。路径两端均为黑洞或白洞，消耗的燃料值不变化。作为压轴题，自然不会是如此简单的最短路问题，所以每过1单位时间黑洞...
02014年5月10日5,957spfa
「BZOJ1641」[Usaco2007 Nov] Cow Hurdles 奶牛跨栏
DescriptionFarmerJohn想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。奶牛的训练场中有N(1≤N≤300)个站台，分别标记为1..N。所有站台之间有M(1≤M≤25,000)条单向路径，第i条路经是从站台Si开始，到站台Ei，其中最高的栏的高度为Hi(1≤Hi≤1,000,0...
12014年4月16日3,974floyd
「POJ1556」The Doors
DescriptionYouaretofindthelengthoftheshortestpaththroughachambercontainingobstructingwalls.Thechamberwillalwayshavesidesatx=0,x=10,y=0,andy=10.Theinitialandfinalpointsofthepatharealways(0,5)and(10,5).Therewillalsobefrom0to18verticalwallsinsidethechamber,eachwithtwodoorways.Thefigurebelowillustratessuchachamberandalsoshowsthepathofminimallength.InputTheinputdatafortheillustratedchamberwould...
02014年4月12日5,785spfa,几何