#include<stdio.h>
#define inf 1000000000

struct arcnode
{
        int             adjvex,
                        len,
                        nextarc;
}list[150000+30000+1+2];
int pos[30000+1];
int heap[30000+1];
int dist[30000+1];
int n,m,qlen;
     
void qup(int u)
{   
     int i=heap[u];
     int p=u>>1;
     int tmp=dist[i];
     while(p>0&&dist[heap[p]]>tmp)
     {
        pos[heap[p]]=u;
        heap[u]=heap[p];
        u>>=1;p>>=1;
     }
     pos[i]=u;
     heap[u]=i;
}

void qdown(int root)
{
    int p,t=heap[root], rc;
    while(p=(root<<1) <= qlen)
    {
        rc =(root<<1+1);
        if(rc <= qlen && dist[heap[rc]] < dist[heap[p]]) p  = rc;
        if(dist[t] > dist[heap[p]] )
        {
            heap[root] = heap[p];
            pos[heap[root]] = root;
        }
        else break;
        root = p;
    }
    heap[root] = t;
    pos[heap[root]] = root;
}

void dij()
{
      for(int i=1;i<=n;i++)
         {
             dist[i]=inf;
             heap[i]=i;
             pos[i]=i;
         }
         dist[1]=0;
         qlen=n;
         while(qlen)
         {   
             int min=heap[1];
             heap[1]=heap[qlen--];
             pos[heap[1]]=1;
             qdown(1);
             int h=list[min].nextarc;         
             while(h)
             {
                int w=dist[min] +list[h].len;
                int v=list[h].adjvex;
                if(dist[v]>w)
                {
                    dist[v]=w;
                    qup(pos[list[h].adjvex]);
               }   
               h=list[h].nextarc;
             }
          }
          printf("%d\n",dist[n]);
}

int main()
{
    freopen("in.txt","r",stdin);
    int a,b,c,l,h,head;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
         for(int i=0,l=n+1;i<m;i++)
         {
             scanf("%d %d %d",&a,&b,&c);
             h=l++;
             list[h].adjvex=b;list[h].len=c;list[h].nextarc=0;
             head=list[a].nextarc;
             if(!head) 
                list[a].nextarc=h;
             else
             {
                while(list[head].nextarc)
                   head=list[head].nextarc;
                list[head].nextarc=h;
             }
         }
         dij();
    } 
    while(1);
    return 0;
}

• Re:我的dij+heap怎么老TLE呢，哪位大牛指点一下 (2556) 1361008482 2011-12-06 21:46:07