用线段树写Dijkstra！！！

void Dijikstra(int s){
  memset(dis,inf,sizeof(dis));
  dis[s]=0;
  for(int i=1;i<=n;++i){
    int maxs=inf,u=0;
    for(int j=1;j<=n;++j)
      if(!vis[j]&&dis[j]<maxs)
        maxs=dis[j],u=j;
    vis[u]=1;
    for(int e=pre[u];e;e=nx[e]){
      const int v=to[e];
      if(dis[v]>dis[u]+w[e])
        dis[v]=dis[u]+w[e];
    }
  }
}

typedef pair<int,int> p;
priority_queue<p,vector<p>,greater<p> > q;
void Dijkstra(int s){
  memset(dis,inf,sizeof(dis));
  dis[s]=0;
  q.push(p(0,s));
  while(!q.empty()){
    const int u=q.top().second;
    q.pop();
    if(!vis[u]){
      vis[u]=1;
      for(int e=pre[u];e;e=nx[e]){
        const int v=to[e];
        if(!vis[v]&&dis[v]>dis[u]+w[e])
          dis[v]=dis[u]+w[e],
          q.push(p(dis[v],v));
      }
    }
  }
}

int tree[N<<2],leaf;
/*线段树存的是点的标号*/
int check(int i,int j){
  return dis[i]<dis[j]?i:j;
}
void build(){
  memset(dis,inf,sizeof(dis));
  for(leaf=1;leaf<=n;leaf<<=1);--leaf;
  for(int i=1;i<=n;++i) tree[leaf+i]=i;
}
/*修改 dis[x] 为 y*/
void change(int x,int y){
  dis[x]=y,x+=leaf,x>>=1;
  while(x) tree[x]=check(tree[x<<1],tree[x<<1|1]),x>>=1;
}
void Dijkstra(int s){
  build();
  dis[s]=0;
  int u=s;
  for(int i=1;i<=n;++i){
    ans[u]=dis[u];
    change(u,max_int); /*删除u*/
    for(int e=pre[u];e;e=nx[e]){
      const int v=to[e];
      if(dis[v]>ans[u]+w[e])
        change(v,ans[u]+w[e]);
    }
    u=tree[1];
  }
}