传送门：
http://poj.org/problem?id=3268
题目大意：
有编号为1－N的牛，它们之间存在一些单向的路径。给定一头牛的编号，其他牛要去拜访它并且拜访完之后要返回自己原来的位置，求这些牛中所花的最长的来回时间是多少。
给出N头牛，M条路，要拜访牛的编号X。
思路：
也就是每头牛都要已最短路径到达X号牛，并且从X号牛再回到自己原处。可以反推，从X号牛开始到每头牛的最短距离，并且再回到X号牛的最短距离。但是你通过原图只能知道每头牛到X号牛回去的路，而不知去的最短路径。可以再用一个数组来存储把每条路径倒过来后的距离，这样就可以求得去的最短路径。最短路径就是用Dijkstra算法套模板就可以。
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1010;
const int INF = 9000000;
bool vis[MAXN];
bool vis1[MAXN];
int map[MAXN][MAXN];
int map1[MAXN][MAXN];
int dis[MAXN];
int dis1[MAXN];
void Dij(int start,int n)
{for(int i = 1; i <= n; i++) {dis[i] = map[start][i];dis1[i] = map1[start][i];vis[i] = false;vis1[i] = false;}dis[start] = 0;dis1[start] = 0;for(int j = 1; j < n; j++) {int k = -1;int k1 = -1;int Min = INF;int Min1 = INF;for(int i = 1; i <= n; i++) {if(!vis[i] && dis[i] < Min) {Min = dis[i];k = i;}if(!vis1[i] && dis1[i] < Min1) {Min1 = dis1[i];k1 = i;}}if(k != -1) {vis[k] = true;for(int i = 1; i <= n; i++) {if(!vis[i] && dis[k] + map[k][i] < dis[i]) {dis[i] = dis[k] + map[k][i];}}}if(k1 != -1) {vis1[k1] = true;for(int i = 1; i <= n; i++) {if(!vis1[i] && dis1[k1] + map1[k1][i] < dis1[i]) {dis1[i] = dis1[k1] + map1[k1][i];} }}}
}
int main()
{int n, m, x;cin >> n >> m >> x;memset( map, INF, sizeof(map));memset( map1, INF, sizeof(map1));for(int i = 1; i <= m; i++) {int a,b,c;scanf("%d%d%d",&a,&b,&c);map[a][b] = c;map1[b][a] = c;} for(int i = 1; i <= n; i++) {map[i][i] = 0;map1[i][i] = 0;}Dij(x,n);int sum;int maxx = -1;for(int i = 1; i <= n; i++) {if(i != x) {sum = dis[i] + dis1[i];if(sum > maxx)maxx = sum;}}cout << maxx << endl; return 0;
}