首页 > 代码库 > poj 3268 Silver Cow Party(dijkstra最短路)
poj 3268 Silver Cow Party(dijkstra最短路)
题目链接:http://poj.org/problem?id=3268
题目大意:给你N个农场,在X农场要举办一个party,其它农场需要到X农场去,然后还要回来,问N个农场中距离最远的那个至少为多少?,给出的边为单向边。。。
思路:用dijkstra最初X农场到其它几个农场的最短距离,然后在把边反向,继续求出X到其它几个农场的最短距离,算出最大的那一个。。。
code:
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<queue> using namespace std; const int maxn=1010; const int INF=1000000000; struct Edge { int from,to,dist; }; struct HeapNode { int d,u; bool operator < (const HeapNode& rhs) const{ return d>rhs.d; } }; struct Dijkstra { int n,m; //点数和边数 vector<Edge> edges; //边列表 vector<int > G[maxn]; //每个节点出发的边编号 bool done[maxn]; //是否已永久标号 int d[maxn]; //s到各点的距离 int p[maxn]; //最短路中的上一条边 void init(int n) //清空 { this->n=n; for(int i=0;i<n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int dist) //增加边 { edges.push_back((Edge){from,to,dist}); m=edges.size(); G[from].push_back(m-1); } void dijkstra(int s) //求s到所以点的距离 { priority_queue<HeapNode> Q; for(int i=0;i<=n;i++) { d[i]=INF; } d[s]=0; memset(done,0,sizeof(done)); Q.push(HeapNode{0,s}); while(!Q.empty()) { HeapNode x=Q.top(); Q.pop(); int u=x.u; if(done[u]) continue; done[u]=true; for(int i=0;i<G[u].size();i++) { Edge& e=edges[G[u][i]]; if(d[e.to]>d[u]+e.dist) { d[e.to]=d[u]+e.dist; p[e.to]=G[u][i]; Q.push((HeapNode){d[e.to],e.to}); } } } } }; int dis[1010],a[100005],b[100005],t[100005]; int main() { Dijkstra D; int n,m,x,i; while(scanf("%d%d%d",&n,&m,&x)==3) { D.init(n); for(i=0;i<m;i++) { scanf("%d%d%d",&a[i],&b[i],&t[i]); D.AddEdge(a[i],b[i],t[i]); } D.dijkstra(x); for(i=1;i<=n;i++) //记录x到所以边的距离 { dis[i]=D.d[i]; } D.init(n); for(i=0;i<m;i++) //增加反向边 { D.AddEdge(b[i],a[i],t[i]); } D.dijkstra(x); int maxx=0; for(i=1;i<=n;i++) { if(dis[i]+D.d[i]>maxx) maxx=dis[i]+D.d[i]; } printf("%d\n",maxx); } return 0; }
poj 3268 Silver Cow Party(dijkstra最短路)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。