题目链接：http://poj.org/problem?id=3268
题目大意：给出n个点和m条边，接着是m条边，代表从牛a到牛b需要花费c时间，现在所有牛要到牛x那里去参加聚会，并且所有牛参加聚会后还要回来，给你牛x，除了牛x之外的牛，他们都有一个参加聚会并且回来的最短时间，从这些最短时间里找出一个最大值输出
解题思路：最短路径只需要从x到i的最短路径代表他们返回的最短路径，然后将所有边反过来，再从x到i的最短路径代表他们来参加聚会的最短路径，这样对应相加找出一个最大值就可以了，当然其实不需要将所有边反过来，只需要将map的行和列对换一下就可以了，数据比较大，所以floyd超时，用dijkstra比较好点
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> #include <queue> using namespace std; bool book1[1222],book2[1222]; int dis1[1222],dis2[1222]; int inf=0x3f3f3f3f,num; int maps[1222][1222],n,x; void Dijstr(int s,int e) { int u1,u2,i; memset(book1,false,sizeof(book1)); memset(book2,false,sizeof(book2)); for(i=1;i<=n;i++) { dis1[i]=maps[x][i]; //x到每个点的距离 dis2[i]=maps[i][x]; //转置矩阵交换行列将去的变成回来的路，就变成其余农场到x的距离。 } book1[x]=true; book2[x]=true; for(i=1;i<n;i++) { int mi1=inf,mi2=inf; for(int j=1;j<=n;j++) { if(mi1>dis1[j]&&!book1[j]) { mi1=dis1[j]; u1=j; } if(mi2>dis2[j]&&!book2[j]) { mi2=dis2[j]; u2=j; } } book1[u1]=true; book2[u2]=true; for(int v=1;v<=n;v++) { if(!book1[v]&&dis1[v]>dis1[u1]+maps[u1][v]) { dis1[v]=dis1[u1]+maps[u1][v]; } if(!book2[v]&&dis2[v]>dis2[u2]+maps[v][u2]) { dis2[v]=dis2[u2]+maps[v][u2]; } } } } int main() { int m,i; int u,v,w; scanf("%d%d%d",&n,&m,&x); memset(maps,inf,sizeof(maps)); for(i=0;i<=n;i++) maps[i][i]=0; for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); maps[u][v]=w; } int ma=-1,sum; Dijstr(n,x); // 每组数据只需要进行一次Dijstr就可以。 for(i=1;i<=n;i++) { if(i==x) continue; sum=dis1[i]+dis2[i];//dis1存储的x到其余点的距离，dis2存储的是其余点到x的距离。 ma=max(sum,ma); // 找到一个最大值存储。 } printf("%d\n",ma); return 0; }