Effective Solution In C (yes, C and not C++) | BEATS 93% | USING DIJKSTRA’S ALGORITHM |
Intuition
The problem requires finding the number of shortest paths from node 0 to node n-1 in a weighted graph.
This suggests using Dijkstra’s algorithm to det
# Intuition
- The problem requires finding the number of shortest paths from node `0` to node `n-1` in a weighted graph. 
- This suggests using **Dijkstra’s algorithm** to determine the shortest path and **dynamic programming** to count the number of ways to reach each node optimally.
---
# Approach
1. **Graph Representation**  
   - The graph is represented as an adjacency list, where each node stores a list of edges (neighboring nodes and weights).

2. **Dijkstra’s Algorithm for Shortest Path**  
   - Use a **distance array (`dist[i]`)** to store the shortest distance from node `0` to each node, initialized to `LLONG_MAX`.
   - Use a **ways array (`ways[i]`)** to count the number of shortest paths leading to each node, initialized to `0`.
   - Use a **priority queue (min-heap)** to process nodes in increasing order of distance.

3. **Relaxation of Edges**  
   - While processing a node, iterate through all its adjacent nodes.
   - If a shorter path to a neighbor is found, update its distance and reset the number of ways.
   - If an equal shortest path is found, add the number of ways from the current node to the neighbor.

4. **Final Result**  
   - The answer is stored in `ways[n-1]`, representing the number of shortest paths to the last node.
---
# Complexity
- **Time complexity:**  
  - Dijkstra’s algorithm runs in $$O((V + E) * log(V))$$ using a priority queue.  
  - Each edge is relaxed once, leading to an overall complexity of $$O(E*log(V))$$

- **Space complexity:**  
  - $$O(V + E)$$ for storing the graph.  
  - $$O(V)$$ for `dist` and `ways` arrays.  
  - $$O(V)$$ for the priority queue.  
  - Overall, $$O(V + E)$$
---
# Code
```c []
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MOD 1000000007

typedef long long ll;

// Structure to represent a node in the priority queue
typedef struct {
    ll distance;
    int node;
} HeapNode;

// Structure to represent the priority queue
typedef struct {
    HeapNode* nodes;
    int size;
    int capacity;
} PriorityQueue;

// Function to create a priority queue
PriorityQueue* createPriorityQueue(int capacity) {
    PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->nodes = (HeapNode*)malloc(capacity * sizeof(HeapNode));
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}

// Function to swap two nodes in the priority queue
void swap(HeapNode* a, HeapNode* b) {
    HeapNode temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify up
void heapifyUp(PriorityQueue* pq, int index) {
    if (index && pq->nodes[index].distance < pq->nodes[(index - 1) / 2].distance) {
        swap(&pq->nodes[index], &pq->nodes[(index - 1) / 2]);
        heapifyUp(pq, (index - 1) / 2);
    }
}

// Function to heapify down
void heapifyDown(PriorityQueue* pq, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < pq->size && pq->nodes[left].distance < pq->nodes[smallest].distance)
        smallest = left;

    if (right < pq->size && pq->nodes[right].distance < pq->nodes[smallest].distance)
        smallest = right;

    if (smallest != index) {
        swap(&pq->nodes[index], &pq->nodes[smallest]);
        heapifyDown(pq, smallest);
    }
}

// Function to push a node into the priority queue
void push(PriorityQueue* pq, ll distance, int node) {
    if (pq->size == pq->capacity) {
        pq->capacity *= 2;
        pq->nodes = (HeapNode*)realloc(pq->nodes, pq->capacity * sizeof(HeapNode));
    }
    pq->nodes[pq->size].distance = distance;
    pq->nodes[pq->size].node = node;
    heapifyUp(pq, pq->size);
    pq->size++;
}

// Function to pop the minimum node from the priority queue
HeapNode pop(PriorityQueue* pq) {
    HeapNode root = pq->nodes[0];
    pq->nodes[0] = pq->nodes[--pq->size];
    heapifyDown(pq, 0);
    return root;
}

// Function to check if the priority queue is empty
int isEmpty(PriorityQueue* pq) {
    return pq->size == 0;
}

// Structure to represent an adjacency list node
typedef struct AdjListNode {
    int dest;
    ll weight;
    struct AdjListNode* next;
} AdjListNode;

// Structure to represent an adjacency list
typedef struct {
    AdjListNode** array;
    int size;
} AdjList;

// Function to create an adjacency list node
AdjListNode* createAdjListNode(int dest, ll weight) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// Function to create an adjacency list
AdjList* createAdjList(int size) {
    AdjList* adjList = (AdjList*)malloc(sizeof(AdjList));
    adjList->array = (AdjListNode**)malloc(size * sizeof(AdjListNode*));
    adjList->size = size;
    for (int i = 0; i < size; i++)
        adjList->array[i] = NULL;
    return adjList;
}

// Function to add an edge to the adjacency list
void addEdge(AdjList* adjList, int src, int dest, ll weight) {
    AdjListNode* newNode = createAdjListNode(dest, weight);
    newNode->next = adjList->array[src];
    adjList->array[src] = newNode;

    newNode = createAdjListNode(src, weight);
    newNode->next = adjList->array[dest];
    adjList->array[dest] = newNode;
}

// Function to free the adjacency list
void freeAdjList(AdjList* adjList) {
    for (int i = 0; i < adjList->size; i++) {
        AdjListNode* node = adjList->array[i];
        while (node) {
            AdjListNode* temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(adjList->array);
    free(adjList);
}

// Function to count the number of ways to arrive at the destination
int countPaths(int n, int** roads, int roadsSize, int* roadsColSize) {
    // Create adjacency list
    AdjList* adjList = createAdjList(n);
    for (int i = 0; i < roadsSize; i++) {
        int u = roads[i][0];
        int v = roads[i][1];
        ll time = roads[i][2];
        addEdge(adjList, u, v, time);
    }

    // Initialize distances and ways
    ll* dist = (ll*)malloc(n * sizeof(ll));
    int* ways = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        dist[i] = LLONG_MAX;
        ways[i] = 0;
    }
    dist[0] = 0;
    ways[0] = 1;

    // Create priority queue
    PriorityQueue* pq = createPriorityQueue(n);
    push(pq, 0, 0);

    // Dijkstra's algorithm
    while (!isEmpty(pq)) {
        HeapNode minNode = pop(pq);
        ll distance = minNode.distance;
        int node = minNode.node;

        if (distance > dist[node])
            continue;

        AdjListNode* adj = adjList->array[node];
        while (adj) {
            int adjNode = adj->dest;
            ll nextDist = adj->weight;

            if (distance + nextDist < dist[adjNode]) {
                dist[adjNode] = distance + nextDist;
                ways[adjNode] = ways[node];
                push(pq, dist[adjNode], adjNode);
            } else if (distance + nextDist == dist[adjNode]) {
                ways[adjNode] = (ways[adjNode] + ways[node]) % MOD;
            }

            adj = adj->next; // Move to the next adjacent node
        }
    }

    int result = ways[n - 1];

    // Free allocated memory
    free(dist);
    free(ways);
    freeAdjList(adjList);
    free(pq->nodes);
    free(pq);

    return result;
}
```
['Math', 'Dynamic Programming', 'Graph', 'Topological Sort', 'Memoization', 'Ordered Map', 'C', 'Combinatorics', 'Prefix Sum', 'Shortest Path']