POJ 3268 Silver Cow Party(双向dijkstra)

题目链接：http://poj.org/problem?id=3268

      题意是有编号为1-n的农场，然后有m条路，再输入一个x。每个农场里都有一头牛，然后让各个农场的牛都到x农场去参加party，结束后再让它们各回各家，当然牛也是很懒的(虽然它憨厚老实)，所以它所走的路都是最短的路，问最后哪头牛走的路最多。

      第一次见这种题，出题角度刁钻，但是我们只需要先正着跑一遍dij，然后再反向建图跑一遍dij就好了(就相当于牛回家的路程)。我直接开了两个数组，其中一个用来反向存图。最后遍历找一个两个路程相加的最大值输出就好了。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#define inf 0x3f3f3f3f
#define maxn 1010
using namespace std;
int pre1[maxn][maxn],pre2[maxn][maxn];
int ans1[maxn],ans2[maxn];
int n,m,x;

void init(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i == j)pre1[i][j] = pre2[i][j] = 0;
			else pre1[i][j] = pre2[i][j] = inf;
		}
	}
}

void dijkstra(int *ans,int pre[maxn][maxn]){
	int Min,flag;
	bool vis[maxn];
	for(int i=1;i<=n;i++){
		vis[i] = 0;
		ans[i] = pre[x][i];
	}
	for(int i=1;i<=n;i++){
		Min = inf;
		for(int j=1;j<=n;j++){
			if(!vis[j] && ans[j] < Min){
				Min = ans[j];
				flag = j;
			}
		}
		vis[flag] = 1;
		for(int j=1;j<=n;j++){
			if(!vis[j] && ans[j] > ans[flag] + pre[flag][j]){
				ans[j] = ans[flag] + pre[flag][j];
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&x);
	init();
	for(int i=0;i<m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		pre1[u][v] = w;
		pre2[v][u] = w;
	}
	dijkstra(ans1, pre1);
	dijkstra(ans2, pre2);
	int ans = -1;
	for(int i=1;i<=n;i++){
		ans = max(ans, ans1[i] + ans2[i]);
	}
	printf("%d\n",ans);
	return 0;
}