【DJ+手打堆板子】WA#1#3#4求hack数据

如题。昨天发过，今天又调了好久，仍然没过。。

测试点过大，找不到错误。

评测记录

代码如下：

#include<cstdio>
#define INF 0x3f3f3f3f
using namespace std;
int min(int a,int b){return a<b?a:b;}
int h[100003];//h[i]:the last out-edge of vertice i
struct tu_edge{
    int a,b,w,n;//st&ed and last out-edge of a
    void input(int i){
        scanf("%d%d%d",&a,&b,&w);
        n=h[a],h[a]=i;
    }
}edge[200003];
int dis[100003];//distance of each vertice to s
int pos[100003];//position in f_queue of each vertice
struct f_queue{
    private:
        int tail,tree[100003];
        void _upper(int x){
            int temp=tree[x];
            pos[tree[x/2]]=x,tree[x]=tree[x/2];
            pos[tree[x]]=x/2,tree[x/2]=temp;
        }
        void _update(int x){
            if(dis[tree[x]]<dis[tree[x/2]]) _upper(x),_update(x/2);
            else{
                if(x*2 >tail) return;
                int temp=x*2;
                if(temp<tail) if(dis[tree[temp]]>dis[tree[temp+1]]) ++temp;
                if(dis[tree[temp]]<dis[tree[x]]) _upper(temp),_update(temp);
            } 
        }
    public:
        void push(int a){
            tree[++tail]=a,pos[a]=tail;
            _update(tail);
        }
        void redate(int a){
            _update(pos[a]);
        }
        int pop(){
            int temp=tree[1];
            pos[tree[1]]=0 ,pos[tree[tail]]=1;
                tree[1] =       tree[tail--];
            _update(1);
            return temp;
        }
        bool empty(){
            return !tail;
        }
}que;
int n,m,s;
int main(){
    //input&pre
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;++i) dis[i]=INF;
    dis[s]=0,que.push(s);
    for(int i=1;i<=m;++i) edge[i].input(i);
    //dj
    while(!que.empty()){
        int temp=que.pop(),tmp;//new blue vertice
//      printf("%d:\n",temp);
        for(int i=h[temp];i;i=edge[i].n){
            tmp=edge[i].b;
            if (dis[tmp]>dis[temp]+edge[i].w) 
                dis[tmp]=dis[temp]+edge[i].w,//printf(" +%d=%d->%d:%d->%d\n",i,edge[i].w,tmp,dis[temp],dis[tmp]),
                pos[tmp]?que.redate(tmp):que.push(tmp);
        }
    }
    for(int i=1;i<=n;++i) printf("%d ",dis[i]);
    return 0;
}

现在初步判断是堆或者堆的使用的问题（？）因为我试了试改成使用STL实现，A了。评测记录。代码如下：

#include<cstdio>
#include<queue>
#define N 1000000
using namespace std;
int n,m,st,dis[N],u[N],h[N];
struct tu_edge{
    int a,b,w,n;//st&ed and last out-edge of a
    void input(int i){
        scanf("%d%d%d",&a,&b,&w);
        n=h[a],h[a]=i;
    }
}edge[200003];
struct dnt{
    int ans,id;
    bool operator<(const dnt &x)const{return x.ans<ans;}
};
priority_queue<dnt> q;
int main(){
    scanf("%d%d%d",&n,&m,&st);
    for(int i=1;i<=m;i++) edge[i].input(i);
    for(int i=1;i<=m;i++) dis[i]=0x3f3f3f3f;
    dis[st]=0,q.push((dnt){0,st});
    while(!q.empty()){
        int temp=q.top().id;q.pop();
        if(u[temp]) continue;
        u[temp]=1;
        for(int i=h[temp];i;i=edge[i].n){
            int tmp=edge[i].b;
            if (dis[tmp]>dis[temp]+edge[i].w){
                dis[tmp]=dis[temp]+edge[i].w;
                if(!u[tmp]) q.push((dnt){dis[tmp],tmp});
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}

然而如果把u的判定删除（也就是每次更新不判定对象是否已经是蓝点）上面那段代码会在#2#3#6出现TLE（疑似死循环，本蒻已经下不了数据了）。评测记录。但是根据DJ的原理，不应该存在能够更新已经是蓝点的节点的情况，这个判定在我看来是无用的，为什么没了不行呢？也希望各位大佬解答一下。