0 ms C/C++, 1 ms JS. BFS and Dijkstra. Beats 100.00%
Approach
BFS 1 ms in JavaScript.
Dijkstra's Algorithm 40 ms in JavaScript.
Complexityv - vertices, e - edges.
Time complexity: BFS O(v3), Dijkstra O((v+e)logv)
# Approach
1. BFS `1 ms` in JavaScript.
2. Dijkstra's Algorithm `40 ms` in JavaScript.

![1.png](https://assets.leetcode.com/users/images/5e00e095-a024-4d36-8a21-3834524032b3_1742787920.1375878.png)

![2.png](https://assets.leetcode.com/users/images/8bf589cb-0abe-4fb3-95a8-974df20f1926_1742788234.092651.png)

![3.png](https://assets.leetcode.com/users/images/7bf74c18-a8db-4c28-9ea7-237cd4645de4_1742788242.533792.png)


# Complexity
$$v$$ - vertices, $$e$$ - edges.
- Time complexity: BFS $$O(v^3)$$, Dijkstra $$O((v + e) log v)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(v^2)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp [C++ BFS 0 ms]
class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        if (n < 3) return 1;
        const int mod = 1e9 + 7;
        const int szn = n * sizeof(long);
        const int sznn = n * n * sizeof(int);
        unsigned long* time = (unsigned long*)alloca(szn);
        unsigned long* count = (unsigned long*)alloca(szn);
        int* m = (int*)alloca(sznn);
        memset(time, 255, szn);
        memset(count, 0, szn);
        memset(m, 0, sznn);

        for (const auto& r : roads)
            m[r[0] * n + r[1]] = m[r[1] * n + r[0]] = r[2];
        time[0] = 0;
        count[0] = 1;
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n - 1; ++i) {
                if (count[i] == 0) continue;
                for (int j = 0; j < n; ++j) {
                    const int tj = m[i * n + j];
                    if (tj == 0) continue;
                    const int tij = time[i] + tj;
                    if (tij < time[j]) {
                        time[j] = tij;
                        count[j] = count[i];
                    } else if (tij == time[j]) {
                        count[j] = (count[j] + count[i]) % mod;
                    }
                }
                count[i] = 0;
            }
        }
        return count[n - 1];
    }
};
```
```c [C BFS 0 ms]
int countPaths(int n, int** roads, int rsize, int* _) {
    if (n < 3) return 1;
    const int mod = 1e9 + 7;
    unsigned long time[n];
    unsigned long count[n];
    int m[n * n];
    memset(time, 255, sizeof(time));
    memset(count, 0, sizeof(count));
    memset(m, 0, sizeof(m));

    for (int i = 0; i < rsize; ++i) {
        const int* r = roads[i];
        m[r[0] * n + r[1]] = m[r[1] * n + r[0]] = r[2];
    }
    time[0] = 0;
    count[0] = 1;
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n - 1; ++i) {
            if (count[i] == 0) continue;
            for (int j = 0; j < n; ++j) {
                const int tj = m[i * n + j];
                if (tj == 0) continue;
                const int tij = time[i] + tj;
                if (tij < time[j]) {
                    time[j] = tij;
                    count[j] = count[i];
                } else if (tij == time[j]) {
                    count[j] = (count[j] + count[i]) % mod;
                }
            }
            count[i] = 0;
        }
    }
    return count[n - 1];
}
```
```javascript [JS BFS 1 ms]
const countPaths = (n, roads) => {
    if (n < 3) return 1;
    const mod = 1e9 + 7;
    const time = new Array(n).fill(Infinity);
    const count = new Array(n).fill(0);
    const m = new Uint32Array(n * n);
    for (const r of roads)
        m[r[0] * n + r[1]] = m[r[1] * n + r[0]] = r[2];
    time[0] = 0;
    count[0] = 1;
    for (let k = 0; k < n; ++k) {
        for (let i = 0; i < n - 1; ++i) {
            if (count[i] === 0) continue;
            for (let j = 0; j < n; ++j) {
                const tj = m[i * n + j];
                if (tj === 0) continue;
                const tij = time[i] + tj;
                if (tij < time[j]) {
                    time[j] = tij;
                    count[j] = count[i];
                } else if (tij === time[j]) {
                    count[j] = (count[j] + count[i]) % mod;
                }
            }
            count[i] = 0;
        }
    }
    return count[n - 1];
};
```
```javascript [JS Dijkstra 40 ms]
const countPaths = (n, roads) => {
    if (n < 3) return 1;
    const mod = 1e9 + 7;
    const time = new Array(n).fill(Infinity);
    const count = new Array(n).fill(0);
    const q = new MinPriorityQueue((tn) => tn[0]);
    const m = new Uint32Array(n * n);
    for (const r of roads)
        m[r[0] * n + r[1]] = m[r[1] * n + r[0]] = r[2];
    time[0] = 0;
    count[0] = 1;
    q.push([0, 0]);
    while (!q.isEmpty()) {
        const tn = q.pop();
        const ti = tn[0];
        const i = tn[1];
        if (ti > time[i]) continue;
        for (let j = 0; j < n; ++j) {
            const tj = m[i * n + j];
            if (tj === 0) continue;
            const tij = ti + tj;
            if (tij < time[j]) {
                time[j] = tij;
                count[j] = count[i];
                q.push([tij, j]);
            } else if (tij === time[j]) {
                count[j] = (count[j] + count[i]) % mod;
            }
        }

    }
    return count[n - 1];
};
```
['Array', 'Dynamic Programming', 'Breadth-First Search', 'Graph', 'C', 'Heap (Priority Queue)', 'Shortest Path', 'C++', 'TypeScript', 'JavaScript']