POJ3268，Silver Cow Party（最短路）

这道题的大概意思就是，有n只奶牛，它们的家的编号为从1到n，编号为x的奶牛要举办party，其它奶牛都要去它家参加，参加完后又要回去，每只奶牛不论是去还是回，都会挑选最短的路径走。最终要从这些奶牛当中，算出他们各自来与回的总时长，并输出最大的那个时间。
此题涉及的图示有向图。显然，奶牛们从x的家回到自己家的过程，可以看成是求单源最短路问题，不过，奶牛们从家里出发到x家，这个过程其实也可以看成是从x家回到自己家，即同样转化为单源最短路问题，**只需要把从i到j的边的权与从j到i的边的权交换一下就好了。**

代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define inf 10000005
using namespace std;
const int maxn=1e3+5;
int map[maxn][maxn],dis_to[maxn],dis_back[maxn];	//用邻接矩阵好写一点。
bool vis[maxn];
void dijkstra(int n,int s)
{
for(int i=1;i<=n;i++)
{
dis_back[i]=map[s][i];
vis[i]=0;
}
vis[s]=1;
for(int i=1;i<=n;i++)
{
int temp=inf,k;
for(int j=1;j<=n;j++)
if(!vis[j]&&temp>dis_back[j])
temp=dis_back[k=j];
if(temp==inf)	break;
vis[k]=1;
for(int j=1;j<=n;j++)
dis_back[j]=min(dis_back[j],dis_back[k]+map[k][j]);
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
swap(map[i][j],map[j][i]);
for(int i=1;i<=n;i++)
{
dis_to[i]=map[s][i];
vis[i]=0;
}
vis[s]=1;
for(int i=1;i<=n;i++)
{
int temp=inf,k;
for(int j=1;j<=n;j++)
if(!vis[j]&&temp>dis_to[j])
temp=dis_to[k=j];
if(temp==inf)	break;
vis[k]=1;
for(int j=1;j<=n;j++)
dis_to[j]=min(dis_to[j],dis_to[k]+map[k][j]);
}
}
int main()
{
int n,x,m;
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)	map[i][j]=inf;
else map[i][j]=0;
for(int i=1;i<=m;i++)
{
int u,v,t;
scanf("%d%d%d",&u,&v,&t);
map[u][v]=t;
}
dijkstra(n,x);
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dis_to[i]+dis_back[i]);
printf("%dn",ans);
return 0;
}

最后

以上就是潇洒乐曲为你收集整理的POJ3268，Silver Cow Party（最短路）的全部内容，希望文章能够帮你解决POJ3268，Silver Cow Party（最短路）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。