oj.uz

Submission #9162

# Submission time Handle Problem Language Result Execution time Memory
9162 2014-09-28T04:13:32 Z yukariko Your life (kriii2_Y) C
4 / 4
 164 ms 21656 KB 
typedef struct node{int w,v;} hDATA;
typedef struct Heap{
  hDATA *arr;
  int count;
  int capacity;
  int (*compare)(hDATA p,hDATA q);
}Heap;
#define MAX_HEAP hMaxCompare
#define MIN_HEAP hMinCompare
int hParent(Heap *h, int i)
{
  if(i<=0||i>=h->count)return -1;
  return (i-1)/2;
}
int hLeftChild(Heap *h, int i)
{
  int t=2*i+1;
  if(t>=h->count)return -1;
  return t;
}
int hRightChild(Heap *h, int i)
{
  int t=2*i+2;
  if(t>=h->count)return -1;
  return t;
}
hDATA hTop(Heap *h)
{
  return h->arr[0];
}
/*int hMaxCompare(hDATA p,hDATA q)
{
  return p>q;
}*/
int hMinCompare(hDATA p,hDATA q)
{
  return p.w<q.w;
}
Heap *CreateHeap(int capacity, int (*compare)(hDATA p,hDATA q))
{
  Heap *h=(Heap *)malloc(sizeof(Heap));
  h->count=0;
  h->capacity=capacity;
  h->compare=compare;
  h->arr=(hDATA *)malloc(sizeof(hDATA)*capacity);
  return h;
}
void DownHeap(Heap *h, int i)
{
  int l,r,max;
  hDATA t;
  l=hLeftChild(h,i);
  r=hRightChild(h,i);
  if(l!=-1&&h->compare(h->arr[l],h->arr[i]))max=l;
  else max=i;
  if(r!=-1&&h->compare(h->arr[r],h->arr[max]))max=r;
  if(max!=i)
  {
    t=h->arr[i];
    h->arr[i]=h->arr[max];
    h->arr[max]=t;
    DownHeap(h,max);
  }
}
void UpHeap(Heap *h, int i)
{
  hDATA data=h->arr[i];
  int p;
  for(p=hParent(h,i);p!=-1&&h->compare(data,h->arr[p]);p=hParent(h,i))
  {
    h->arr[i]=h->arr[p];
    i=p;
  }
  h->arr[i]=data;
}
hDATA hDelete(Heap *h)
{
  hDATA data={0};
  if(h->count==0)return data;
  data=h->arr[0];
  h->arr[0]=h->arr[h->count-1];
  h->count--;
  DownHeap(h,0);
  return data;
}
void hDeleteIndex(Heap *h,int i)
{
  if(h->count==0||i>=h->count)return;
  h->arr[i]=h->arr[h->count-1];
  h->count--;
  UpHeap(h,i);
}
void ResizeHeap(Heap *h)
{
  hDATA *arr_old=h->arr;
  int i;
  h->arr=(hDATA *)malloc(sizeof(hDATA)*h->capacity*2);
  for(i=0;i<h->capacity;i++)h->arr[i]=arr_old[i];
  h->capacity*=2;
  free(arr_old);
}
int hInsert(Heap *h, hDATA data)
{
  if(h->count==h->capacity)ResizeHeap(h);
  h->arr[h->count++]=data;
  UpHeap(h,h->count-1);
}
void DestroyHeap(Heap *h)
{
  if(h==0)return;
  free(h->arr);
  free(h);
}
void BuildHeap(Heap *h,hDATA A[], int n)
{
  if(h==0)return;
  while(n>h->capacity)ResizeHeap(h);
  int i;
  for(i=0;i<n;i++)
  {
    h->arr[i]=A[i];
  }
  h->count=n;
  for(i=(n-1)/2;i>=0;i--)DownHeap(h,i);
}

typedef struct pair{int w,v;} qData;
typedef struct LinkedList{
  qData data;
  struct LinkedList *next;
} LinkedList;
typedef struct Queue{
  LinkedList *head;
  LinkedList *tail;
  int count;
} Queue;
Queue *CreateQueue()
{
  Queue *q = (Queue *)malloc(sizeof(Queue));
  q->head=(LinkedList *)malloc(sizeof(LinkedList));
  q->head->next=0;
  q->tail=q->head;
  q->count=0;
  return q;
}
void qPush(Queue *q,qData data)
{
  q->tail->data=data;
  q->tail->next=(LinkedList *)malloc(sizeof(LinkedList));
  q->tail=q->tail->next;
  q->tail->next=0;
  q->count++;
}
qData qPop(Queue *q)
{
  qData data=q->head->data;
  LinkedList *p=q->head;
  q->head=q->head->next;
  q->count--;
  free(p);
  return data;
}

hDATA make_pair(int w,int v)
{
  hDATA data;
  data.w=w;
  data.v=v;
  return data;
}
qData make_qpair(int w,int v)
{
  qData data;
  data.w=w;
  data.v=v;
  return data;
}

int N,E;
int isINF;
const int INF=987654321;
Queue *adj[100001];
Dijkstra(int r,int end)
{
  int dist[N+1];
  int i,j,k,w,v;
  hDATA data;
  
  for(i=1;i<=N;i++)dist[i]=INF;
  dist[r]=0;
  
  Heap *heap=CreateHeap(N+1,MIN_HEAP);
  hInsert(heap,make_pair(0,r));
  for(;heap->count;)
  {
    data=hDelete(heap);
    w=data.w;
    v=data.v;
    
    if(dist[v]<w)continue;
    LinkedList *p=adj[v]->head;
    for(i=0;i<adj[v]->count;i++)
    {
      if(dist[p->data.v] > w+p->data.w)
      {
        dist[p->data.v]=w+p->data.w;
        hInsert(heap,make_pair(w+p->data.w,p->data.v));
      }
      p=p->next;
    }
  }
  DestroyHeap(heap);
  return dist[end]==INF?-1:dist[end];
}

main()
{
  scanf("%d%d",&N,&E);
  int i,j;
  for(i=1;i<=N;i++)adj[i]=CreateQueue();
  int x,y,w;
  for(i=0;i<E;i++)
  {
    scanf("%d%d",&x,&y);
    qPush(adj[x],make_qpair(1,y));
    qPush(adj[y],make_qpair(1,x));
  }
  printf("%d",Dijkstra(1,N));
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1868 KB Output is correct
2 Correct 0 ms 1868 KB Output is correct
3 Correct 0 ms 1868 KB Output is correct
4 Correct 0 ms 1868 KB Output is correct
5 Correct 0 ms 1868 KB Output is correct
6 Correct 0 ms 1868 KB Output is correct
7 Correct 0 ms 1868 KB Output is correct
8 Correct 0 ms 1868 KB Output is correct
9 Correct 0 ms 1868 KB Output is correct
10 Correct 32 ms 8072 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9116 KB Output is correct
2 Correct 52 ms 15324 KB Output is correct
3 Correct 96 ms 18360 KB Output is correct
4 Correct 80 ms 17300 KB Output is correct
5 Correct 84 ms 17828 KB Output is correct
6 Correct 84 ms 15320 KB Output is correct
7 Correct 100 ms 15320 KB Output is correct
8 Correct 164 ms 21656 KB Output is correct
9 Correct 80 ms 16904 KB Output is correct
10 Correct 152 ms 21656 KB Output is correct