最短路

cf689B题目链接 题意：n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1（注意近路不一定就近） 思路：一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2N蠢哭。。。实际上应该3M…因为连相邻的边是双向的。。。再加上近路的单向。。。然后spfa就好了。。。。

hdu3873题目链接 题意：n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。 思路：。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。

1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 250 Solved: 178 [Submit][Status][Discuss] Description # A crime has been comitted: a load of grain has been taken from the barn by one of FJ’s cows. FJ is trying to determine which of his C (1 <= C <= 100) cows is the culprit. Fortunately, a passing satellite took an image of his farm M (1 <= M <= 70000) seconds before the crime took place, giving the location of all of the cows. He wants to know which cows had time to get to the barn to steal the grain. Farmer John’s farm comprises F (1 <= F <= 500) fields numbered 1..F and connected by P (1 <= P <= 1,000) bidirectional paths whose traversal time is in the range 1..70000 seconds (cows walk very slowly). Field 1 contains the barn. It takes no time to travel within a field (switch paths). Given the layout of Farmer John’s farm and the location of each cow when the satellite flew over, determine set of cows who could be guilty. NOTE: Do not declare a variable named exactly ’time’. This will reference the system call and never give you the results you really want.

1631: [Usaco2007 Feb]Cow Party # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 670 Solved: 493 [Submit][Status][Discuss] Description # 农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条路需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？ Input # 第1行：三个用空格隔开的整数.

http://codeforces.com/problemset/problem/602/C 题意：给出n个城镇，m条双向铁路，对于任意不同的x,y，如果x,y之间没有铁路，那么一定有双向公路。train只能走铁路，bus只能走公路。现在一辆火车和一辆bus同时从1出发，要到达n，处于安全考虑，bus和火车不能同时处在除了n以外的点。bus和train不要求同时到达。任意一段道路的时间花费都是1小时。问最少需要多久使得bus和train都到达n。如果存在某个不能到达，那么输出-1. 思路：n才400.一开始打算先按照rail和road建两个图。这两个图互为补。然后在floyd的时候加以判断。但是马上就发现。。不能同时到达同伙一个点这个条件其实不会影响。。因为按照题意，一定存在一条1到n的路，不是公路就是铁路。那么就让有路的花费1的代价到n，然后剩下的求一个一到n的最短路即可。由于n才400.。最短路怎么搞都行。。我偷懒就用floyd了。