zoj 1857 Fire Station

zoj 1857 Fire Station

#include <iostream>#include <stdio.h>#include <stdlib.h>#include <memory.h>#include <limits.h>#include <queue>#define N 600using namespace std; struct adjlist{    int length;    int num;    struct adjlist *next;};struct dist{    int num;    int length;};typedef  struct adjlist adj;typedef  struct dist d;adj *p[N],node[N*N],*head[N];d tempdis[N],temp;int point[N];int heap_size; void heappaixu(d a[],int i){    int l_child,r_child,larg;    d temp;    while(1)    {        l_child = i<<1;        r_child = l_child+1;        if( l_child <= heap_size && a[l_child].length < a[i].length ) larg = l_child;        else larg = i;        if(r_child <= heap_size && a[r_child].length < a[larg].length)        { larg = r_child;        }        if( larg != i )        { point[a[i].num] = larg; point[a[larg].num] = i; temp = a[i]; a[i] = a[larg]; a[larg] = temp;  i = larg;        }        else  break;    }}void Insertheap(d a[],d key){    int i,parent;    d temp;    heap_size++;    a[heap_size] = key;    i = heap_size;    while( i>1 )    {        parent = i>>1;        if( a[i].length < a[parent].length )        { point[a[i].num] = parent; point[a[parent].num] = i; temp = a[i]; a[i] = a[parent]; a[parent] = temp; i = parent;        }        else break;    }}void Delheap(d a[]){    point[a[heap_size].num] = 1;    a[1] = a[heap_size];    heap_size--;    heappaixu(a,1);}  int main(void){    int fnum,n,i,j,now,min,max,fresum,sum,k,mmax;    int hash[N],fire,x,y,length,flag[N];    int count,to,tempj,mark,dis[N],t[N];    char str[50];    while( scanf("%d %d",&fnum,&n)!= EOF )    {        memset( p,'',sizeof(p) );        memset( flag,0,sizeof(flag) );        memset( dis,0,sizeof(dis));        mark = 0;        for(i=1; i<=fnum; i++)         { scanf("%d",&fire); flag[fire] = 1; dis[fire] = 0;        }        getchar();        count = 1;        while( gets(str) && strlen(str) )         { sscanf(str,"%d%d%d",&x,&y,&length); node[count].num = y; node[count].length = length; node[count].next = p[x]; p[x] = &node[count]; count++; node[count].num = x; node[count].length = length; node[count].next = p[y]; p[y] = &node[count]; count++;        }        for(i=1; i<=n; i++) head[i] = p[i];        for(j=1; j<=n; j++)        { if(flag[j] == 0)     mark = 1;        }        if( mark == 0 )        { printf("1n"); continue;        }        max = INT_MAX;        for(i=1; i<=n; i++)        { head[i] = p[i];  }        for(i=1; i<=n; i++) if( !flag[i] )     dis[i] = INT_MAX;     memcpy(t,dis,(n+1)*sizeof(int));        for(j=1; j<=n; j++)        {  if( flag[j] == 1 )     continue;        memcpy(dis,t,(n+1)*sizeof(int)); memset( point,0,sizeof(point) ); memset( hash,0,sizeof(hash) ); mmax = 0;  heap_size = 0; now = j; dis[now] = 0;hash[now] = 1; for(i=1; i<=n; i++)     head[i] = p[i]; for(k=1; k<=n; k++)     head[k] = p[k]; for(k=1; k<=n; k++)     if( flag[k] )     {         dis[k] = 0;         temp.length = 0;         temp.num = k;         Insertheap(tempdis,temp);         point[k] = heap_size;         hash[k] = 1;     } for(i=1; i<=n; i++)    {     while( head[now]!= NULL )     {         to = head[now]->num;         if( dis[to] > dis[now] + head[now]->length )         {  dis[to] = dis[now] + head[now]->length;  if( hash[to] == 1 )  {      tempdis[point[to]].length = dis[to];  }  else  {      temp.length = dis[to];      temp.num = to;      Insertheap(tempdis,temp);      point[to] = heap_size;      hash[to] = 1;  }         }         head[now] = head[now]->next;     }      now = tempdis[1].num;     Delheap(tempdis); }   for(k=1; k<=n; k++)     if( dis[k] > mmax )     {         mmax = dis[k];     } if( max > mmax ) {     max = mmax;     tempj = j; }         }        printf("%dn",tempj);     }  return 0;}