最短路 - Page 4

「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,564dijkstra

「BZOJ2324」[ZJOI2011] 营救皮卡丘
Description皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。由于火箭队的重重布防，要想摧毁K号据点，必须按照顺序先摧...
02014年10月9日7,622费用流,floyd
「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,443dijkstra
「BZOJ3402」[Usaco2009 Open] Hide and Seek 捉迷藏
Description 贝茜在和约翰玩一个“捉迷藏”的游戏．她正要找出所有适合她躲藏的安全牛棚．一共有N(2≤N≤20000)个牛棚，被编为1到N号．她知道约翰（捉牛者）从牛棚1出发．所有的牛棚由M(1≤M≤50000)条双向路连接，每条双向路连接两个不同的牛棚．所有的牛棚都是相通的．贝茜认为同牛棚1距离最远的的牛棚是安全的．两个牛棚间的距离是指，从一个牛棚到另一个牛棚最少需要通过的道路数量．请帮贝茜找出所有的安...
02014年9月26日3,476dijkstra
「POJ1734」Sightseeing trip
DescriptionThereisatravelagencyinAdeltontownonZanzibarisland.Ithasdecidedtoofferitsclients,besidesmanyotherattractions,sightseeingthetown.Toearnasmuchaspossiblefromthisattraction,theagencyhasacceptedashrewddecision:itisnecessarytofindtheshortestroutewhichbeginsandendsatthesameplace.Yourtaskistowriteaprogramwhichfindssucharoute.InthetownthereareNcrossingpointsnumberedfrom1toNandMtwo-wayr...
02014年9月24日3,817floyd
「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,697dijkstra
「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,569dijkstra
「BZOJ2662」[BJ WC2012] 冻结
Description “我要成为魔法少女！”“那么，以灵魂为代价，你希望得到什么？”“我要将有关魔法和奇迹的一切，封印于卡片之中„„”在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。现在，不需要立下契约也可以使用魔法了！你还不来试一试？比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。例如，我们熟知的Cirno，她的冰...
02014年8月13日4,708dijkstra
「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,874dijkstra
「BZOJ2346」[Baltic 2011] Lamp
Description2255是一个傻X，他连自己家灯不亮了都不知道。某天TZ大神路过他家，发现了这一情况，于是TZ开始行侠仗义了。TZ发现是电路板的问题，他打开了电路板，发现线路根本没有连上！！于是他强大的脑力可以使某个格子上的线路从\变为/，或者从/变为\。2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。如果无法变亮，输出“NOSOLUTION”。n,m<=500SampleInput...
02014年8月5日3,455dijkstra
「BZOJ2304」[APIO2011] 寻路path
DescriptionTooDee是一块二维格子状的土地（就像著名的笛卡尔坐标系那样），在这里生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物，它们只在二维活动，而且它们非常的文明开化。TooDee的蜂窝和正常世界的蜂窝也是很不一样的，它们是矩形的且它们的边平行于TooDee的地理坐标系，就是说矩形的边或者是东西走向，或者是南北走向。因为Dees是很高级的生物，它们有很多固定的飞行轨道，这些轨道由一些平行于坐标轴的线段组成，...
02014年8月5日7,170模拟,spfa,dijkstra,线段树
「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日3,205dijkstra