zercal

  1 #include<iostream>
  2 using namespace std;
  3 #define maxn 100000
  4 #define maxint 100000000
  5 
  6 struct adj{
  7     int ed;
  8     int ll;
  9     adj *pe;
 10 };
 11 
 12 int vn,maxd;//点数 需要将vn赋初值 
 13 int dui[maxn],d[maxn],father[maxn],hx[maxn];//点，堆从1开始 
 14 struct adj *node[maxn];//邻接表 ，要memset 
 15 
 16 int take(int x)
 17 {
 18     int k;
 19     while(d[dui[x]]<d[dui[x/2]]&&x>1)
 20     {
 21         swap(hx[dui[x]],hx[dui[x/2]]);
 22         swap(dui[x],dui[x/2]);
 23         x=x/2;
 24     }        
 25     while((x*2)<=maxd)
 26     {
 27         k=x*2;
 28         if(k<maxd&&d[dui[k]]>d[dui[k+1]])
 29             k++;
 30         if(d[dui[x]]>d[dui[k]])
 31         {
 32             swap(hx[dui[x]],hx[dui[k]]);
 33             swap(dui[x],dui[k]);
 34             x=k;
 35         }
 36         else    break;
 37     }
 38     return 0;
 39 }
 40 
 41 int out()
 42 {
 43     int x,i;
 44     if(maxd<1) return -1;
 45     x=dui[1];
 46     dui[1]=dui[maxd--];
 47     take(1);
 48     return x;
 49 }
 50 
 51 
 52 int djs(int st,int ee)
 53 {
 54     int i,j,k,x;
 55     adj *p;
 56     maxd=vn;
 57     for(i=1;i<=vn;i++)
 58     {
 59         dui[i]=i;
 60         d[i]=maxint;
 61         hx[i]=i;
 62     }
 63     d[st]=0;
 64     father[st]=st;
 65     take(hx[st]);
 66     x=out();
 67     while(x!=-1)
 68     {
 69         if(x==ee) break;
 70         p=node[x];
 71         while(p!=NULL)
 72         {
 73             if(d[p->ed]>d[x]+p->ll)
 74             {
 75                 d[p->ed]=d[x]+p->ll;
 76                 father[p->ed]=x;
 77                 take(hx[p->ed]);
 78             }
 79             p=p->pe;
 80         }
 81         x=out();
 82     }
 83     return d[ee];
 84 }
 85 
 86 int insert(int a,int b,int c)
 87 {
 88     adj *p;
 89     p=node[a];
 90     node[a]=(adj*)malloc(sizeof(adj));
 91     node[a]->ed=b;
 92     node[a]->ll=c;
 93     node[a]->pe=p;
 94     return 0;
 95 }
 96 
 97 
 98 
 99 
100 
101 
102