为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/comehome
目录 |
[编辑] 分析
这道题的规模很小（52），所以可以用Floyd-Warshall算法求出所有点对的最短路，然后找出其中到'Z'距离最短的点就可以了。
当然本题也可以用Dijkstra来做，会比Floyd快一些，不过编程复杂度要高一些。
思路二：借鉴广度优先搜索的思想。code已给出。
建立图的邻接表存储，每次访问展节点c时，对其相连的顶点v进行检查，若有dis['Z',c]+dis[c,v]<dis['Z',v] 则dis['Z',v]:=dis['Z',c]+dis[c,v]; 如果节点v未访问 则进队。
只需进行一次宽度优先搜索即可。 (……其实我想说，dijkstra的核心思想不就是贪心+BFS吗。)
注意！！！！两个牧场之间可能有多条路径！！！我因为这样WA了一次！！（这个问题。。是因为储存方法的局限性。。。如果用邻接矩阵的话好主意考虑数据的重边。） 值得注意的是，由于有10000条边，而总共只有52个节点，也就是说，输入中的许多边都是没有用的，所以读入的时候应该判断一下这条边已有的权值是否比读入的权值要小，如果小的话，再赋值。
思路三：使用深度优先搜索。 从"Z"开始深搜，记录到达每个点的最短路径，方法其实与dijkstra类似，也是找单源最短路径，编程比dijkstra简单一些。 由于52个点，时间限制几乎可以不考虑了。 全部是0.00s通过的。
看叻这么多题解，终于轮到我发了..（激动、、）
本题差不多是一个裸的单源最短路，用Dijkstra、Floyd、SPFA做都可以，其中Floyd是N三方，Dijkstra和SPFA都是N平方，但因为数据范围很小（只有52个字母），用哪一种都可以，我用的是SPFA，实际复杂度比N平方要低（所有数据均可以在0.00s过），而且较容易实现，两点之间有多条边也没关系，不用邻接矩阵就行了，用一个存边的邻接表就OK，不会影响到求最短路。
具体做法反正就是一个裸的最短路，代码我放后面了，最后输出值最小且不在['a'..'z']中、不等于Z的点就可以了。
/* 表示SPFA是O(kE)，E就是边数(p)，k的平均值为2。所以效率SPFA是最低的-.-|| ——Dirak */
[编辑] 思路：
题目要求求出从 pasture 到 barn 的最短路径，spfa，dijkstra 等等的算法都可以，那么可以倒过来思考，从终点‘Z’出发，求出起点‘Z’到各 pasture 的最短路径即可，注意题目输入有重边，需要判重！
