POJ 3268 Silver Cow Party 最短路 dijkstra

题目

题意：给出n个点和m条边，接着是m条边，代表从牛a到牛b需要花费c时间，现在所有牛要到牛x那里去参加聚会，并且所有牛参加聚会后还要回来，给你牛x，除了牛x之外的牛，他们都有一个参加聚会并且回来的最短时间，从这些最短时间里找出一个最大值输出

题解：这题说是从所有点到x，可以看成是从x到所有点的最短路，注意来回的方向是不同的，所以用两遍dijkstra，一遍是一个方向。

代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#define inf 100000
using namespace std;
int vis[1005],mp[1005][1005],dis1[1005],dis2[1005],tar,n,k;
void dijkstra(){
int i,m,x,j;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)dis1[i]=dis2[i]=inf;
dis1[tar]=dis2[tar]=0;
for(i=1;i<=n;i++){
x=0,m=inf;
for(j=1;j<=n;j++){
if(!vis[j]&&dis1[j]<m){
x=j;
m=dis1[j];
}
}
vis[x]=1;
for(j=1;j<=n;j++){
if(!vis[j])
dis1[j]=min(dis1[j],dis1[x]+mp[x][j]);
}
}
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++){
x=0,m=inf;
for(j=1;j<=n;j++){
if(!vis[j]&&dis2[j]<m){
x=j;
m=dis2[j];
}
}
vis[x]=1;
for(j=1;j<=n;j++){
if(!vis[j])
dis2[j]=min(dis2[j],dis2[x]+mp[j][x]);
}
}
return ;
}
int main()
{
int x,y,w,i,j;
scanf("%d%d%d",&n,&k,&tar);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)mp[i][j]=inf;
while(k--){
scanf("%d%d%d",&x,&y,&w);
mp[x][y]=w;
}
dijkstra();
int maxn=0;
for(i=1;i<=n;i++)maxn=max(maxn,dis1[i]+dis2[i]);
printf("%dn",maxn);
return 0;
}

最后

以上就是虚心哑铃为你收集整理的POJ 3268 Silver Cow Party 最短路 dijkstra的全部内容，希望文章能够帮你解决POJ 3268 Silver Cow Party 最短路 dijkstra所遇到的程序开发问题。

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