[Usaco2007 Feb]Cow Party

### 回答1：
题目描述

有N头奶牛，它们在M个牛棚之间相互转移。每个牛棚里有一些奶牛，每分钟可以容纳一头奶牛。一头奶牛从一个牛棚走到另一个牛棚需要一分钟的时间。现在，这些奶牛要开一个牛派对，它们要在同一时间到达同一个牛棚，所以它们需要在某个牛棚等待一段时间。你需要计算最小的等待时间，使得所有奶牛都能够在同一时间到达同一个牛棚。

输入格式

第一行包含三个整数N，M，X。

接下来M行，每行包含三个整数a，b，t，表示牛棚a和牛棚b之间有一条双向边，需要t分钟才能通过。

输出格式

输出一个整数，表示最小等待时间。

数据范围

1≤N≤500
1≤M≤10000
1≤X≤N
1≤a,b≤N
1≤t≤1000

输入样例#1

3 3 1
1 2 5
2 3 5
1 3 10

输出样例#1

5

输入样例#2

4 5 4
1 2 10
2 3 10
3 4 10
4 1 10
1 3 20

输出样例#2

30

算法1

(最短路) $O(N^3)$

Dijkstra算法
Dijkstra（迪杰斯特拉）算法是由荷兰计算机科学家狄克斯特拉于1956年发明的，因此又叫狄克斯特拉算法。

Dijkstra算法是一种贪心算法，用于求解一个节点到其他所有节点的最短路径。它的主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止。

具体做法是：设立一个数组dis来保存源点到各个顶点的最短距离和一个数组book[i]来记录一个顶点是否已经在队列中。

初始时，原点s的路径权重被赋为0 （dis[s] = 0）。若对于顶点s存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，所有顶点并不属于任何已知最短路径所包含的顶点集合，因此都被标记为未知最短路径长度。当算法结束时，dis[v]中存储的便是源点s到顶点v的最短路径，或者如果从s无法到达v，则值为INF。
Dijkstra算法流程：

算法流程：
1. 将所有顶点分为两部分：已知最短路的顶点集合P和未知最短路的顶点集合Q。
2. 初始时，顶点集合P中只有源点s一个元素，以源点s为起点向外扩展。
3. 每次从顶点集合Q中选取一个顶点u（u的dist最小），并加入到顶点集合P中，同时以u为中心进行扩展。
4. 重复步骤3，直到顶点集合Q为空或者终点被加入到顶点集合P中。
5. 算法结束，最短路径保存在dis数组中。

时间复杂度

Dijkstra算法的时间复杂度为O(N^2)。由于N较小，因此可以通过本题。

参考文献

Dijkstra算法讲解

C++ 代码

算法2

(最短路) $O(N^2)$

Floyd算法
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

Floyd算法的基本思想

设G=(V,E)是一个带权有向图，其邻接矩阵为W。V={v1,v2,……,vn}，W[1:n,1:n]，则该图的Floyd算法可描述如下：

时间复杂度

Floyd算法的时间复杂度为O(N^3)。由于N较小，因此可以通过本题。

参考文献

Floyd算法讲解

C++ 代码

算法3

(最短路) $O(N^2)$

Bellman-Ford算法
Bellman-Ford算法是一种单源最短路径算法，可以处理负权边，但不能处理负权回路。

Bellman-Ford算法的基本思想

对于图中的任意一条边(u, v)，Bellman-Ford算法会对每一条边进行一次松弛操作（Relax），并且这些操作是按照顺序进行的：当算法进行第i次松弛操作时，它只会改变长度为i+1的路径上的顶点的值。因此，当算法执行完第n-1次松弛操作后，路径长度最长不超过n-1，此时所有最短路径都已经求出。

时间复杂度

Bellman-Ford算法的时间复杂度为O(N*M)。由于N和M的范围较小，因此可以通过本题。

参考文献

Bellman-Ford算法讲解

C++ 代码

### 回答2：
Usaco 2007 Feb的问题是关于Cow Party的。这个问题中，农夫约翰有N头奶牛，它们之间通过一些路径相互连接，并且每个路径都有一个长度。约翰想要在某个时间将它的所有奶牛聚集在一起举办一个派对，现在他想知道所有奶牛从各自的位置到达聚会地点所需的最短时间。

为了解决这个问题，我们可以使用Dijkstra算法。我们首先需要创建一个节点集合，包含所有的奶牛和派对地点，并且初始化每个节点的最短时间为无穷大。接下来，我们选取一个起点节点--聚会地点，并将它的最短时间设置为0。然后我们开始遍历所有的节点，每次选择一个最短时间未确定的节点，并更新它的邻居节点的最短时间。我们重复这个过程，直到所有节点的最短时间都确定。

在更新节点的最短时间时，我们需要根据节点之间的路径长度来更新。我们检查从当前节点到邻居节点的路径长度加上当前节点的最短时间是否小于邻居节点目前的最短时间。如果是，则更新邻居节点的最短时间为新的最短时间。

最后，我们可以得到所有奶牛到达聚会地点所需的最短时间。我们找到所有奶牛起始位置的最长最短时间，即为我们的答案。

通过使用Dijkstra算法，我们可以解决这个问题并得到最优解。因此，Usaco 2007 Feb的Cow Party问题可以通过这种方法解决。