CSES - Investigation

Time Complexity: $\mathcal{O}(E\log V)$

We can run Dijkstra keeping track of the distance: $dist[]$, the number of ways with the minimum distance: $num[]$, the minimum flights with the minimum distance: $minf[]$, and the maximum flights with the minimum distance: $maxf[]$. For every node, $v$, we take into consideration all of its neighbors, $u$. If we can reach $u$ in a shorter distance than its current minimum, we update the distance and reset $num[u]$, $minf[u]$, and $maxf[u]$. We also have to take into consideration if we can reach $u$ in an equivalent distance. If so, we update:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<pair<ll, int>> edge[100001];
ll dist[100001]; ll num[100001];
int minf[100001];int maxf[100001];
bool v[100001];
ll MAX = 1000000000000000L; ll MOD = 1000000007L;
void djikstra(int s){