POJ 3268 Silver Cow Party (Dijkstra~)

http://poj.org/problem id=3268

N只母牛（起始地点不同）要去X这个地方，给出有向图，要求求出他们到x后并且返回（不一定原路，有向图）的路程最大的母牛（算的是来回），

其中他们走到x和从x返回走的路径均是最短的。

思路：

从x到每个点的最短路径还算好求。直接Dijkstra即可

但是从每个点到x呢？

难道要n次Dijkstra？或者floyd？

不，那样效率太低了！

一个方法是进行矩阵转置，然后再来一次Dijkstra即可。

为什么这样可以？对于有向图，本来是从n个点到x的，你转置一下相当于x到n个点了。

很巧妙吧？

#include
  
   
#include
   
     using namespace std; const int MAXN=1010; const int INF=99999; int map[MAXN][MAXN]; int n,m,x; void map_reverse() { for(int i=1;i<=n;i++) for(int j=1;j
    
      ans) ans=temp; } printf("%d\n",ans); } return 0; }