Cod sursa(job #1504512)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 17 octombrie 2015 20:33:29
Problema Algoritmul lui Dijkstra Scor 80
Compilator c Status done
Runda Arhiva educationala Marime 2.02 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];

int fst = 0, lst = 0;
node * coada[100001];

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;

  coada[lst++] = & nodes[start];

  while (fst <= lst) {
    node * crt = coada[fst++];

    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;

	coada[lst++] = &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;
	coada[lst++] = &nodes[curenta->catre];
      }
    }      
  }

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