POJ3268 Silver Cow Party(最短路径)

题意：

每个农场有一头牛，现在要到农场x开派对，路径是单向的，要求开完派对后还要回到原农场，求所有牛的最短路径的最大值

要点：

就是一个定终点求最短路径的变形，现在已经知道终点，从终点回到原农场的最短路径很好求，直接dijkstra算法即可，想求原农场到终点的最短路径只要将所有的单向路反向即可。利用函数的参量传递可以比较方便的求出。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 0x3f3f3f3f
int n, m, start;
int map[1005][1005], mapt[1005][1005];
int d1[1005], d2[1005];
bool vis[1005];void dijkstra(int x,int mapx[][1005],int dis[])//利用参量传递
{memset(vis, true, sizeof(vis));for (int i = 1; i <= n; i++)dis[i] = mapx[x][i];vis[x] = false;int min, temp;for (int i = 1; i <= n; i++){min = INF;for (int j = 1; j <= n;j++)if (vis[j] && min > dis[j]){temp = j;min = dis[j];}vis[temp] = false;for (int j = 1; j <= n; j++)if (vis[j] && dis[temp] + mapx[temp][j] < dis[j])dis[j] = dis[temp] + mapx[temp][j];}
}int main()
{scanf("%d%d%d", &n, &m, &start);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){if (i == j)map[i][j] = mapt[i][j] = 0;elsemap[i][j] = mapt[i][j] = INF;//开两个路径记录数组，节省了时间}while (m--){int a, b, t;scanf("%d%d%d", &a, &b, &t);map[a][b] = t;mapt[b][a] = t;}dijkstra(start, map,d1);dijkstra(start, mapt, d2);int max = -1;for (int i = 1; i <= n; i++){if (max < d1[i]+d2[i])max = d1[i]+d2[i];}printf("%d\n", max);return 0;
}