Cod sursa(job #1504520)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 17 octombrie 2015 20:46:06
Problema Algoritmul lui Dijkstra Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 3.35 kb
#include<stdio.h>
#include<stdlib.h>

#define RED 0
#define YELLOW 1
#define GREEN 2

typedef struct {
  // 0 -> Red
  // 1 -> Yellow
  // 2 -> Green
  int color;

  // If color == 1 || 2
  int dist;

  int number;
} node;

typedef struct mc {
  int catre;
  int cost;

  struct mc *next;
} muchie;

node nodes[50001];
muchie * muchii[50001];

node heap[500000];
int length;
 
void swap (node *a, node *b) {
  node tmp = *a;
  *a = *b;
  *b = tmp;
}
 
void sift_up (int idx) {
  if (idx == 0)
    return;
   
  int father = (idx - 1) / 2;
     
  if (heap[idx].dist < heap[father].dist) {
    swap (&heap[idx], &heap[father]);
    sift_up (father);
  }
}
 
void push_heap (node val) {
  heap[length++] = val;
  sift_up (length - 1);
}
 
void sift_down (int idx) {
  int fst_son = 2 * idx + 1;
  int snd_son = 2 * idx + 2;
 
  if (fst_son >= length)
    return;
  else if (snd_son >= length) {
    if (heap[idx].dist >= heap[fst_son].dist)
      swap (&heap[idx], &heap[fst_son]);
 
    return;
  }
 
  if (heap[idx].dist > heap[fst_son].dist && heap[idx].dist > heap[snd_son].dist) {
    if (heap[fst_son].dist < heap[snd_son].dist) {
      swap (&heap[idx], &heap[fst_son]);
      sift_down (fst_son);
    }
    else {
      swap (&heap[idx], &heap[snd_son]);
      sift_down (snd_son);
    }
  } else {
    if (heap[idx].dist > heap[fst_son].dist) {
      swap (&heap[idx], &heap[fst_son]);
      sift_down (fst_son);
    } else if (heap[idx].dist >= heap[snd_son].dist) {
      swap (&heap[idx], &heap[snd_son]);
      sift_down (snd_son);      
    }     
  }    
}
 
node pop_heap () {
  node result = heap[0];
 
  heap[0] = heap[--length];
  sift_down(0);
   
  return result;
}
 
node top_heap () {
  return heap[0];
}

void add_edge (int from, int to, int cost) {
  if (muchii[from] == NULL) {
    muchii[from] = (muchie *) malloc (sizeof (muchie));
    muchii[from]->catre = to;
    muchii[from]->cost = cost;
    muchii[from]->next = NULL;
  } else {
    muchie *new = (muchie *) malloc (sizeof (muchie));
    new->catre = to;
    new->cost = cost;

    new->next = muchii[from];
    muchii[from] = new;
  }
}

int main(int argc, char *argv[]) {
  freopen ("dijkstra.in", "r", stdin);
  freopen ("dijkstra.out", "w", stdout);

  int n, m;
  scanf ("%d%d", &n, &m);
  
  int i;  
  for (i = 0; i < m; ++i) {
    int from, to, cost;
    scanf ("%d%d%d", &from, &to, &cost);

    add_edge (from, to, cost);
    //add_edge (to, from, cost);
  }

  for (i = 1; i <= n; ++i) {
    nodes[i].number = i;
    nodes[i].color = RED;
  }

  int start = 1;

  nodes[start].color = YELLOW;
  nodes[start].dist = 0;

  push_heap (nodes[start]);

  while (length != 0) {
    node myTop = pop_heap();
    node * crt = &nodes[myTop.number];

    if (crt == NULL)
      continue;
    
    crt->color = GREEN;

    muchie *curenta;
    for (curenta = muchii[crt->number]; curenta != NULL; curenta = curenta->next) {
      if (nodes [curenta->catre].color == RED) {
	nodes [curenta->catre].color = YELLOW;
	nodes [curenta->catre].dist = crt->dist + curenta->cost;

	push_heap (nodes[curenta->catre]);
      } else if (/*nodes [curenta->catre].color == YELLOW && */
		 nodes [curenta->catre].dist > crt->dist + curenta->cost) {

	nodes [curenta->catre].dist = crt->dist + curenta->cost;
	push_heap (nodes[curenta->catre]);
      }
    }      
  }

  for (i = 2; i <= n; ++i)
    printf ("%d ", nodes[i].dist);
  printf ("\n");
  
  return 0;
}