#include <stdio.h>
#include <stdlib.h>
#define inf 9999999
typedef struct listNode{
// Nodul cu care are muchie detinatorul listei
int node;
// Costul dintre detinatorul listei si node
int cost;
struct listNode *next;
} listNode;
typedef struct graph{
// Numarul de noduri ale grafului
int nodes;
// adj_heads[i] -> lista de adiacenta a nodului i
listNode **adj_heads;
} graph;
typedef struct heap{
int *arr;
int size;
}heap;
heap *createHeap(int n)
{
heap *new = malloc(sizeof(heap));
new->arr = calloc(n, sizeof(int));
new->size = 0;
}
int getLeftChild(int index)
{
return 2 * index + 1;
}
int getRightChild(int index)
{
return 2 * index + 2;
}
int getParent(int index)
{
return (index - 1) / 2;
}
void swap(heap *h, int i, int j)
{
int temp = h->arr[i];
h->arr[i] = h->arr[j];
h->arr[j] = temp;
}
int hasLeftChild(heap *h, int index)
{
return getLeftChild(index) < h->size;
}
int hasRightChild(heap *h, int index)
{
return getRightChild(index) < h->size;
}
void heapifyUp(heap *h, int index)
{
if(index)
{
int parent = getParent(index);
if(h->arr[parent] < h->arr[index])
{
swap(h, parent, index);
heapifyUp(h, parent);
}
}
}
void insert(heap *h, int x)
{
h->arr[h->size] = x;
heapifyUp(h, h->size);
h->size++;
}
void heapifyDown(heap *h, int index)
{
int leftChild = getLeftChild(index);
int rightChild = getRightChild(index);
int max = index;
if(hasLeftChild(h, index) && h->arr[leftChild] > h->arr[max]) max = leftChild;
if(hasRightChild(h, index) && h->arr[rightChild] > h->arr[max]) max = rightChild;
if(max != index)
{
swap(h, max, index);
heapifyDown(h, max);
}
}
void addEdge(graph *g, int v1, int v2, int cost)
{
listNode *new;
new = (listNode *) malloc(sizeof(listNode));
new->node = v2;
new->cost = cost;
new->next = g->adj_heads[v1];
g->adj_heads[v1] = new;
}
void removeEdge(graph *gl, int v1, int v2)
{
listNode *prev, *cur;
cur = gl->adj_heads[v1];
if(cur->node == v2)
{
listNode *aux = cur;
cur = cur->next;
gl->adj_heads[v1] = cur;
free(aux);
}
while(cur)
{
if(cur->node == v2) break;
prev = cur;
cur = cur->next;
}
if(!cur) return;
if(cur->next == NULL)
{
prev->next = NULL;
free(cur);
return;
}
prev->next = cur->next;
free(cur);
}
graph *createGraph(int nodes)
{
graph *g = (graph*) malloc(sizeof(graph));
g->nodes = nodes;
g->adj_heads = (listNode**) calloc(nodes + 1, sizeof(listNode*));
return g;
}
void dijkstra(graph *g, heap *h, int source, int d[], int poz[])
{
for ( int i = 1; i <= g->nodes; ++i )
if(i != source) d[i] = inf, poz[i] = -1;
poz[source] = 1;
h->arr[h->size++] = source;
while(h->size)
{
int min = h->arr[0];
swap(h, 0, h->size - 1);
poz[h->arr[0]] = 1;
h->size--;
heapifyDown(h, 0);
listNode *it = g->adj_heads[min];
while (it)
{
if (d[it->node] > d[min] + it->cost)
{
d[it->node] = d[min] + it->cost;
if (poz[it->node] != -1)
heapifyUp(h, poz[it->node] - 1);
else
{
h->arr[h->size++] = it->node;
poz[h->arr[h->size - 1]] = h->size;
heapifyUp(h, h->size - 1);
}
}
it = it->next;
}
}
}
int main()
{
graph *g;
heap *h;
FILE *fin = fopen("dijkstra.in", "r");
FILE *fout = fopen("dijkstra.out", "w");
int N, M, v1, v2, cost, d[10000], q[10000], min, X, rep[1000], ans;
fscanf(fin, "%d%d", &N, &M);
g = createGraph(N);
h = createHeap(N);
for(int i = 1; i <= M; i++)
{
fscanf(fin, "%d%d%d", &v1, &v2, &cost);
addEdge(g, v1, v2, cost);
}
for(int i = 1; i <= N; i++)
fprintf(fout, "%d ", d[i] == inf ? 0 : d[i]);
fprintf(fout, "\n");
return 0;
}
Danescu Lucian lucidanescu28