cf689B题目链接

题意：n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1（注意近路不一定就近）

思路：一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2N蠢哭。。。实际上应该3M...因为连相邻的边是双向的。。。再加上近路的单向。。。然后spfa就好了。。。。

hdu3873题目链接

题意：n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。

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 …

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牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？

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的时候加以判断。但是马上就发现。。不能同时到达同伙一个点这 …