Floyd

题目链接 题意：有n扇门，n种钥匙，一一对应。每扇门打开后可能得到k把钥匙（k可能为0）。一扇门还可以用一颗炸弹炸开。现在问要开所有门，使用炸弹的期望个数。

hdu2448 题目链接 题意：n 艘船 n 个港口，一个港口只能承接一艘船，m 个油田，给出 n 艘船各自在哪个油田，然后给出 m 个油田之间的无向图，然后给出油田和港口之间的有向图。求 n 艘船到达港口的最小距离之和。

poj 2594 题目链接 题意：一个DAG图，每个点有宝藏…可以降落任意个机器人到任意点…然后机器人可以沿着路径走，路过某个点的时候，可以取走该点的宝藏。问要取走所有宝藏，最少需要多少个机器人。

poj1932题目链接 题意：初始在点 1，有 100 点能量，然后每个点有一个能量值【-100,100】，经过某个点会加上这个点的能量值，问能否找到一条到点 n 的路线，且路径上任何点的能量值一直为正。一共不超过 100 个点。

1641: [Usaco2007 Nov]Cow Hurdles 奶牛跨栏 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 531 Solved: 344 [Submit][Status][Discuss]

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 507 Solved: 345 [Submit][Status][Discuss]

1612: [Usaco2008 Jan]Cow Contest奶牛的比赛 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 900 Solved: 597 [Submit][Status][Discuss]

题目链接 题意：有一条n个节点的链，节点i和节点j的距离为abs(i-j) 现在新增加三条边，距离也都为1，然后给出m个询问，每组询问给出两个点s,t，问s,t之间的最短距离。 思路：比赛的时候没搞出来。 观察特点，对于大多数点来说，都是没有直接的改变，只是增加了三条边。总的思路是：之前s到t的距离为abs(s-t)，通过枚举中间经过的特殊点，观察是否能使得距离减小。

http://poj.org/problem?id=3660 题意：给定n个奶牛，m个奶牛的关系，a,b表示a比b强…问能确定多少个奶牛的排名。 思路：最重要的一点是。。能确定奶牛i的排名的条件是。。知道奶牛i和其他n-1个奶牛的关系。。不管是能打败奶牛i也好。。会被奶牛i打败也好。。只要不是不确定就行。。所以我们跑一遍floyd做传递闭包。得到任何两个点之间的联系。然后对于每一个点。看其他n-1个点是否和他有关系。

http://codeforces.com/contest/500/problem/B 题意：给定一个1至n的数的一种排列。给定一个n*n的矩阵，a[i][j]==0代表pi,pj不可以交换，a[i][j]为1代表p[i],p[j]可以交换。 问字典序最小的排列。。

A - Frogger **Time Limit:**1000MS **Memory Limit:**65536KB 64bit IO Format:%I64d & %I64u Submit Status Description Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping. Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps. To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence. The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.