dijkstra优化

发表于 | 分类于 ， | 阅读数 次

优化

  • dijkstra
  • 注意到贪心的过程是每次选取最小的dis值出来，这里是O(n)的，我们可以用优先队列把他优化到O(logn) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef pair<int,int> l;
priority_queue<s,vector<s>,greater<s> >q;
int dijkstra(int s,int t){
    while(!q.empty())q.pop();
    memset(d,0x3f,sizeof(d));
    memset(in,0,sizeof(0));
    d[s]=0;in[s]=1;
    q.push(l(0,s));
    while(!q.empty()){
        int k=q.top().second;
        q.pop();
        in[k]=1;
        for(int i=head[k];i!=-1;i=e[i].nxt)if(d[k]+e[i].w<d[i]){
            d[i]=e[i].w+d[k];
            if(!in[e[i].t])q.push(l(d[i],e[i].t));
        }
    }
    return d[t]!=inf?d[t]:-1;
}