首页 > 代码库 > POJ - 3268 Silver Cow Party（dijkstra技巧）
POJ - 3268 Silver Cow Party（dijkstra技巧）
题目链接：http://poj.org/problem?id=3268
题意：n只奶牛（分别在1-n奶牛舍）分别从各自的奶牛舍出发到X奶牛舍，然后回到自己的奶舍（都以最短路），求出哪一只奶牛花费的距离最远。
题解：n到达1000，想直接Floyd肯定不行。
从X奶牛舍回家，就直接以X为源点最短路就可以了；从各自的奶牛舍去X奶牛舍可以以X为源点反方向进行求最短路。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <vector> 5 #include <queue> 6 using namespace std; 7 8 const int N=1111; 9 const int INF=0x3f3f3f3f;10 int d1[N],d2[N];11 vector < pair<int,int> > E1[N];12 vector < pair<int,int> > E2[N];13 14 void init(){15 for(int i=0;i<N;i++) d1[i]=INF,d2[i]=INF; 16 }17 18 void dijkstra(int d[],int st,vector < pair<int,int> > E[]){19 priority_queue < pair<int,int> > Q;20 d[st]=0;21 Q.push(make_pair(-d[st],st));22 while(!Q.empty()){23 int now=Q.top().second;24 Q.pop();25 for(int i=0;i<E[now].size();i++){26 int v=E[now][i].first;27 int D=E[now][i].second;28 if(d[v]>D+d[now]){29 d[v]=D+d[now];30 Q.push(make_pair(-d[v],v));31 }32 }33 }34 }35 36 int main(){37 int n,m,x;38 scanf("%d %d %d",&n,&m,&x);39 int a,b,c;40 for(int i=0;i<m;i++){41 scanf("%d %d %d",&a,&b,&c);42 E1[a].push_back(make_pair(b,c));43 E2[b].push_back(make_pair(a,c));44 }45 init();46 int ans=-1;47 dijkstra(d1,x,E1);48 dijkstra(d2,x,E2);49 for(int i=1;i<=n;i++) ans=max(ans,d1[i]+d2[i]);50 printf("%d",ans);51 return 0;52 }
POJ - 3268 Silver Cow Party（dijkstra技巧）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。