[ad_1]

trying to implement a Dijkstra algorithm for my homework.

Faced the “Memory Limit exceedeed” error.

Please tell me what I’m doing wrong.

StatementYou are to write a program that receives a weighted directed graph and finds all distances from fixed vertex S to all

other vertices. Distance from S to some vertex W is the minimal length

of path going from S to W. Length of path is the sum of weights of its

arcs.

Inputfile contains two integers N, M and S. Vertices are numbered

with integer numbers from 1 to N. S is the number of source vertex. M

is the number of arcs. Each of next M lines contain three integers —

numbers of starting and ending vertices of some arc and its weight

respectively. All weights are positive. There is at most one arc

connecting two vertices in every direction.

Outputfile must contain N numbers. Each I-th number is the distance

from vertex S to vertex I. If some vertices are not reachable from S,

corresponding numbers must be −1.

Constraints1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample test:

5 3 1

1 2 5

1 3 7

3 4 10

Out: 0 5 7 17 -1

My programm:

```
#include <stdio.h>
#include <stdlib.h>
#define INF 100001
typedef enum {max, min} Heap_type;
typedef struct {
Heap_type type;
int *data, size;
} Heap;
Heap init_heap(Heap_type type, int size){
Heap * heap = (Heap*)malloc(sizeof(Heap));
if (heap!=NULL)
{
heap->data = (int *) malloc(size * sizeof(int));
heap->type = type;
heap->size = 0;
}
return *heap;
}
void swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
void sift_up(Heap *heap, int id){
heap->size++;
while(heap->type == max ? (heap->datahttps://stackoverflow.com/q/72432586 > heap->data[(id - 1) / 2]) : (heap->datahttps://stackoverflow.com/q/72432586 < heap->data[(id - 1) / 2])){
swap(&(heap->datahttps://stackoverflow.com/q/72432586), &(heap->data[(id - 1) / 2]));
id = (id - 1) / 2;
}
}
void sift_down(Heap *heap, int id){
int child_l, child_r, child_tmp;
while(2 * id + 1 < heap->size){
child_l = 2 * id + 1;
child_r = 2 * id + 2;
child_tmp = child_l;
if(child_r < heap->size)
if(heap->type == max ? heap->data[child_r] > heap->data[child_l] : heap->data[child_r] < heap->data[child_l])
child_tmp = child_r;
if(heap->type == max ? heap->datahttps://stackoverflow.com/q/72432586 >= heap->data[child_tmp] : heap->datahttps://stackoverflow.com/q/72432586 <= heap->data[child_tmp])
break;
swap(&(heap->datahttps://stackoverflow.com/q/72432586), &(heap->data[child_tmp]));
id = child_tmp;
}
}
void push(Heap *heap, int num){
heap->data[heap->size] = num;
sift_up(heap, heap->size);
}
int get_root(Heap *heap){
int root = heap->data[0];
heap->size--;
heap->data[0] = heap->data[heap->size];
sift_down(heap, 0);
return root;
}
void fast_dijkstra(int s, int *d, int n, int m, int **W, Heap pq){
for (int i = 0; i<n; i++)
d[i] = INF;
d[s] = 0;
push(&pq, s);
while (pq.size){
int v = get_root(&pq);
for(int u = 0; u<n; ++u) {
if (W[v][u] && (d[v] + W[v][u]) < d[u]) {
d[u] = d[v] + W[v][u];
push(&pq, u);
}
}
}
}
int main() {
FILE *inp = fopen("input.txt", "r"),
*out = fopen("output.txt", "w");
int N, M, S;
fscanf(inp, "%d %d %d", &N, &M, &S);
S -= 1;
int **W = (int **)malloc(N*sizeof(int *));
for(int i = 0; i < N; i++) {
W[i] = (int *)calloc(N, sizeof(int));
}
for (int _=M; _; _--){
int from, to, path;
fscanf(inp,"%d %d %d", &from, &to, &path);
W[from - 1][to - 1] = path;
}
Heap pq = init_heap(min,N);
int d[N];
fast_dijkstra(S, d, N, M, W, pq);
for (int i = 0; i<N; ++i)
fprintf(out, "%d ", d[i] != INF ? d[i] : -1);
return 0;
}
```

[ad_2]