Dijicstra

#include<stdlib.h>
#include<stdio.h>
#include<limits.h>
#include <stdbool.h>

#pragma warning (disable : 4996)

#define Amsterdam   0
#define DenHaag     1
#define DenHelder   2
#define Utrecht     3
#define Eindhoven   4
#define Maastricht  5
#define Nijmegen    6
#define Zwolle      7
#define Leeuwarden  8
#define Enschede    9
#define Groningen   10
#define Meppel      11

struct Graph {
    int** matrix;
    int size;
};

struct pair {
    int first;
    int second;
};

struct priorityQueue {
    struct pair* data;
    int size;
    int maxSize;
};

struct priorityQueue createPriority(int maxSizeArg) {
    struct priorityQueue toReturn;

    toReturn.data = (struct pair*)malloc(maxSizeArg * sizeof(struct pair));

    toReturn.size = 0;
    toReturn.maxSize = maxSizeArg;

    return toReturn;
}

void push(struct priorityQueue* q, int vertex, int dist) {
    if (q->size == q->maxSize)
        return;

    int index = -1;

    for (int i = 0; i < q->size; i++) {
        if (q->data[i].second > dist) {
            index = i;
            break;
        }
    }

    if (index == -1) {
        q->data[q->size].first = vertex;
        q->data[q->size].second = dist;
        q->size++;
        return;
    }

    for (int i = index; i < q->size + 1; i++)
        q->data[i + 1] = q->data[i];

    q->size++;

    q->data[index].first = vertex;
    q->data[index].second = dist;
}

struct pair pop(struct priorityQueue* q) {
    // if(q->size == 0)
    //     return struct pair(-1, -1);

    struct pair toReturn;
    toReturn.first = q->data[0].first;
    toReturn.second = q->data[0].second;

    for (int i = 0; i < q->size - 1; i++)
        q->data[i] = q->data[i + 1];

    q->size--;

    return toReturn;
}

struct Graph createGraph(int dim) {
    struct Graph toReturn;

    toReturn.matrix = (int**)(malloc(dim * sizeof(int*)));

    for (int i = 0; i < dim; i++)
        toReturn.matrix[i] = (int*)malloc(dim * sizeof(int));

    for (int i = 0; i < dim; i++)
        for (int j = 0; j < dim; j++)
            toReturn.matrix[i][j] = -1;


    toReturn.size = dim;

    return toReturn;
}

void addEdge(struct Graph* g, int start, int end, int weigth) {
    if (start < 0 || start > g->size || end < 0 || end > g->size)
        return;

    g->matrix[start][end] = weigth;
    g->matrix[end][start] = weigth;
}

struct Graph createPlayground(struct pair* removePairs, int size) {
    struct Graph playground = createGraph(12);

    addEdge(&playground, Amsterdam, DenHaag, 46);
    addEdge(&playground, Amsterdam, DenHelder, 77);
    addEdge(&playground, Amsterdam, Utrecht, 26);
    addEdge(&playground, DenHaag, Eindhoven, 89);
    addEdge(&playground, Eindhoven, Maastricht, 63);
    addEdge(&playground, Eindhoven, Nijmegen, 55);
    addEdge(&playground, Eindhoven, Utrecht, 47);
    addEdge(&playground, Enschede, Zwolle, 50);
    addEdge(&playground, Groningen, Leeuwarden, 34);
    addEdge(&playground, Groningen, Meppel, 49);
    addEdge(&playground, Leeuwarden, Meppel, 40);
    addEdge(&playground, Maastricht, Nijmegen, 111);
    addEdge(&playground, Meppel, Zwolle, 15);
    addEdge(&playground, Nijmegen, Zwolle, 77);
    addEdge(&playground, Utrecht, Zwolle, 51);

    for (int i = 0; i < size; i++)
        addEdge(&playground, removePairs[i].first, removePairs[i].second, -1);

    return playground;
}

void freeGraph(struct Graph* g) {
    for (int i = 0; i < g->size; i++)
        free(g->matrix[i]);

    free(g->matrix);
}

void freeQueue(struct priorityQueue* q) {
    free(q->data);
}

bool isEmpty(struct priorityQueue* q) {
    return (q->size == 0);
}

int Dijkstra(struct Graph* g, int startVertex, int endVertex) {
    if (startVertex < 0 || startVertex > g->size)
        return INT_MAX;

    int* distances = (int*)malloc(g->size * sizeof(int));

    for (int i = 0; i < g->size; i++) {
        distances[i] = INT_MAX;
    }

    struct priorityQueue q = createPriority(25);

    distances[startVertex] = 0;

    push(&q, startVertex, 0);

    while (!isEmpty(&q)) {
        struct pair minimumNode = pop(&q);

        int currentVertex = minimumNode.first;
        int distFromStart = minimumNode.second;

        for (int i = 0; i < g->size; i++) {
            if (g->matrix[currentVertex][i] >= 0) {
                if (distances[i] > g->matrix[currentVertex][i] + distances[currentVertex]) {
                    distances[i] = g->matrix[currentVertex][i] + distances[currentVertex];
                    push(&q, i, distances[currentVertex]);
                }
            }
        }
    }

    freeQueue(&q);

    int res = distances[endVertex];
    free(distances);
    return res;
}

int main() {
    int numberOfTowns = 0;
    scanf("%d", &numberOfTowns);

    struct pair* towns = (struct pair*)malloc(numberOfTowns * sizeof(struct pair));

    for (int i = 0; i < numberOfTowns; i++) {
        int fst = 0;
        int snd = 0;

        scanf("%d%d", &fst, &snd);
        towns[i].first = fst;
        towns[i].second = snd;
    }

    struct Graph g = createPlayground(towns, numberOfTowns);

    bool running = true;

    while (running) {
        int cmd = 0;

        scanf("%d", &cmd);

        if (cmd == -1)
            running = false;

        int cmdSnd = 0;
        scanf("%d", &cmdSnd);

        int res = Dijkstra(&g, cmd, cmdSnd);

        printf("%d", res);
    }

    freeGraph(&g);
    free(towns);
}