堆优化的dijkstra

 1 struct node
 2 {
 3     int id,dis;
 4     bool operator < (const node &rhs) const
 5     {
 6         return dis>rhs.dis;
 7     }
 8 } ;
 9 priority_queue<node>q;
10 void dijkstra(int s)
11 {
12     for(int i=1;i<=n;i++)v[i]=0,d[i]=inf;
13     d[s]=0;
14     q.push((node){s,0});
15     while(!q.empty())
16     {
17         node ff=q.top();q.pop();
18         if(v[ff.id]==1) continue;
19         v[ff.id]=1;
20         for(int i=h[ff.id];i;i=e[i].ne)
21         {
22             if(d[ff.id]+e[i].c<d[e[i].v])
23             {
24                 d[e[i].v]=d[ff.id]+e[i].w;
25                 q.push((node){e[i].v,d[e[i].v]});
26             }        
27         }
28     }
29 }