首页 > 其他 > 详细

Dijkstra优先队列模板

时间:2016-07-29 21:24:54      阅读:279      评论:0      收藏:0      [点我收藏+]
 1 struct Node
 2 {
 3     int x,d;
 4     Node(int a,int b){x=a;d=b;}
 5     bool operator < (const Node & a) const
 6     {
 7         return d>a.d;
 8     }
 9 };
10 vector<Node>g[mx];
11 int ds[mx];
12 int n,m;
13 
14 void dijk()
15 {
16     priority_queue<Node>q;
17     q.push(Node(1,0));
18     while (!q.empty())
19     {
20         Node N=q.top();q.pop();
21         for (int i=0;i<g[N.x].size();i++)
22         {
23             Node y=g[N.x][i];
24             if (ds[y.x]>y.d+N.d)
25             {
26                 ds[y.x]=y.d+N.d;
27                 q.push(Node(y.x,ds[y.x]));
28             }
29         }
30     }
31 }

 

Dijkstra优先队列模板

原文:http://www.cnblogs.com/pblr/p/5719610.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!