学步园

此题的实际模型如下：给定一个有P个顶点的无向含权图，选择一个顶点，使得从该点到给定的N个顶点的权值之和最小。

最经典的就是Dijkstra算法了。这个经典的不能再经典的贪心策略，应该都知道的吧。每次都需要在Distance数组中寻求一个最小值，如果图很大，则在此处花费的时间会很多，而堆则可以在O(1)的时间内求得最小值，并且维护一个堆所需的时间都是在log级的。因此考虑把Distance数组的值用堆来存储。

用堆操作的Dijkstra的思想还是与一般的思想类似：

初始化Distance[]=MAX，然后将源点t放入堆中(这就与Distance[t]=0类似)，再从堆中找出一个最小值没有被确定的点minp(就是Distance[minp]=MAX)，将其确定下来，Distance[minp]=mins，mins为从堆中取出来的那个最小值，接着由这个最小值所连接的点求出从源点到这些点的路径长，若所连接的点没有求出最小值，Distance[i]=MAX，则将这个点放入堆中，这就好比用for循环去修改每一个Distance[]的值，不同的地方在于堆中存放的是源点到各个顶点的最小值，如果刚求出来的顶点在Distance[]中已经被赋值了，说明求出来的肯定不是最小值，就像普通Dijkstra的Mark[]一样，mark过的点是不能再被计算的，所以不能放Distance[]中有值的点。这样Dijkstra的部分就完成了。

Dijkstra算法真的是简洁优雅的典范，也可以看出，大学里的《数据结构》这么课学好了，走出学校后确实是很厉害的，寻径算法在现实中出现频率还是很高的。

另外一种方法是改进的BFS算法：

可以理解为动态规划，不过也不是严格的动态规划。你可以写出下面的递推式：

Distance(start, now) = Min(Distance(start, k) + Distance(k, now),  for k in start's adjacnet list)

但如果这个式子是有问题的，请见下面的广搜加深搜的说明。但有问题可以想办法解决，一种办法是：对于枚举的每个牧场 i，令Distance[j]表示 i 到 j 的距离，初始值为INT_MAX，其中Distance[i]=0。维护一个队列，初始为q[1]=i，由队首枚举其他的牧场
j 更新牧场 i 到 j 的最短距离并同时拓展队列。直到队列空为止。这样就求出了点i到所有点的最短距离。和BFS差不多吧，但不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，这个算法中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。

其实也可以广搜加上深搜：

基本思路还是和上面说的BFS一致，主要还是因为一个点被修改后，位于它上层的点也可能受到影响，它上层的上层的点也可能收到影响，这个就是DFS的回溯的。

1. /*
2. ID:fairyroad
3. LANG:C++
4. TASK:butter
5. */
6. #include<fstream>
7. #include<cstring>
8. #include<queue>
9. #include <limits>
10. using namespace std;
11.  
12. ifstream fin("butter.pushed");
13. ofstream fout("butter.out");
14.  
15. const int MAX = 805;
16.  
17. struct vertex
18. {
19.         int end,len;
20. };
21. vertex adj[MAX][MAX];
22.  
23. int cnt[MAX]={0},
    cowpos[505]={0},
    n, p, c;
24. bool pushed[MAX]={0};
25. int distance[MAX];
26.  
27. int search(int start)
28. {
29.         memset(pushed, 0, sizeof(pushed));
30.         for(int k = 1; k <= p; k++)
31.                 distance[k] = numeric_limits<int>::max();
32.        
33.         queue<int> Q;
34.         Q.push(start);
35.         pushed[start] = true;
36.         distance[start] = 0;
37.         while(!Q.empty())
38.         {
39.                 int x = Q.front();
40.                 Q.pop();
41.                 pushed[x] = false;
42.                 for(int j = 0; j < cnt[x]; j++)
43.                 {
44.                         if(distance[x]+adj[x][j].len < distance[adj[x][j].end])
45.                         {
46.                                 distance[adj[x][j].end] = distance[x]+adj[x][j].len;  
47.                                 if(!pushed[adj[x][j].end])
48.                                 {
49.                                         Q.push(adj[x][j].end);
50.                                         pushed[adj[x][j].end] = true;
51.                                 }
52.                         }
53.                 }
54.         }
55.        
56.         int ans = 0;
57.  
58.         for(int i = 1; i<=n; i++)
59.         {
60.                 if(distance[cowpos[i]]==numeric_limits<int>::max()) return -1;
61.                 else  ans+=distance[cowpos[i]];
62.         }
63.         return ans;
64. }
65.  
66. int main()
67. {
68.         memset(cnt, 0, sizeof(cnt));
69.         fin>>n>>p>>c;
70.         for(int i = 1; i<=n; i++)
71.                 fin>>cowpos[i];
72.  
73.         for(int i = 1,
    s, t, value; i <= c; i++)
74.         {
75.                 fin>>s>>t>>value;
76.                 adj[s][cnt[s]].end = t; adj[s][cnt[s]].len = value; cnt[s]++;
77.                 adj[t][cnt[t]].end = s; adj[t][cnt[t]].len = value; cnt[t]++;
78.         }
79.  
80.         int res, min = numeric_limits<int>::max();
81.         for(int i = 1; i <= p; i++)
82.         {
83.                 res = search(i);
84.                 if(res < min && res != -1) min
     =  res;
85.         }
86.        
87.         fout<<min<<endl;
88.         return 0;
89. }