pb_ds的优先队列实现dijkstra

用pb_ds的优先队列来做dijkstra。。据说noip能用哟。

先来篇关于仿函数的文章。

由于pb_ds支持由迭代器访问元素，并且push操作会返回一个迭代器，merge操作会更新迭代器，相当于帮你实现了根据编号找元素的功能（每个元素对应一个迭代器）。但是由于dijkstra在取出堆顶元素以后还要知道堆顶元素的编号，于是我们可以自己搞一个结构体，然后弄一个仿函数。。这样就完成了。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <functional>
  4 #include <ext/pb_ds/priority_queue.hpp>
  5 using namespace std;
  6 
  7 const int maxn=10005, maxm=5e6+5, INF=2147483647;
  8 
  9 struct heap_node{
 10     int value, id;
 11 };
 12 
 13 struct cmp{
 14     bool operator() (heap_node a, heap_node b){
 15         return a.value>b.value;
 16     }
 17 };
 18 
 19 __gnu_pbds::priority_queue<heap_node, cmp> heap;
 20 __gnu_pbds::priority_queue<heap_node, cmp>::point_iterator p[maxn];
 21 
 22 struct Edge{
 23     int to, next, v;
 24 };
 25 
 26 class Graph{
 27 private:
 28     int n, cntedge;
 29     int fir[maxn];
 30     Edge edge[maxm], link[maxn];
 31 public:
 32     Graph(){
 33         n=0, cntedge=0;
 34         memset(fir, 0, sizeof(fir));
 35         memset(edge, 0, sizeof(edge));
 36     }
 37 
 38     void addedge(int x, int y, int z){
 39         ++cntedge;
 40         edge[cntedge].to=y;
 41         edge[cntedge].v=z;
 42         edge[cntedge].next=fir[x];
 43         fir[x]=cntedge;
 44         return;
 45     }
 46 
 47     Edge *get_link(int x){
 48         int nowedge, nowson, cntlink=0;
 49         for (nowedge=fir[x]; nowedge;
 50              nowedge=edge[nowedge].next){
 51             nowson=edge[nowedge].to;
 52             ++cntlink;
 53             link[cntlink]=edge[nowedge];
 54         }
 55         link[0].v=cntlink;
 56         return link;
 57     }
 58 
 59 };
 60 
 61 int n, m, s;
 62 int dis[maxn];
 63 Graph g;
 64 
 65 int main(){
 66     for (int i=0; i<maxn; ++i)
 67         dis[i]=INF;
 68     scanf("%d%d%d", &n, &m, &s);
 69     int f, gg, w;
 70     for (int i=0; i<m; ++i){
 71         scanf("%d%d%d", &f, &gg, &w);
 72         g.addedge(f, gg, w);
 73     }
 74     heap_node ht;
 75     for (int i=1; i<=n; ++i){
 76         ht.id=i, ht.value=INF;
 77         p[i]=heap.push(ht);
 78     }
 79     dis[s]=0;
 80     ht.id=s, ht.value=0;
 81     heap.modify(p[s], ht);
 82     int now, nowson;
 83     Edge *link;
 84     for (int i=0; i<n; ++i){
 85         ht=heap.top();
 86         heap.pop();
 87         if (ht.value==INF) break;
 88         now=ht.id;
 89         link=g.get_link(now);
 90         for (int i=1; i<=link[0].v; ++i){
 91             nowson=link[i].to;
 92             if (dis[now]+link[i].v<dis[nowson]){
 93                 dis[nowson]=dis[now]+link[i].v;
 94                 ht.id=nowson, ht.value=dis[nowson];
 95                 heap.modify(p[nowson], ht);
 96             }
 97         }
 98     }
 99     for (int i=1; i<=n; ++i){
100         printf("%d ", dis[i]);
101     }
102     return 0;
103 }