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:

1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5vector<pair<ll, int>> edge[100001];
6ll dist[100001]; ll num[100001];
7int minf[100001];int maxf[100001];
8bool v[100001];
9ll MAX = 1000000000000000L; ll MOD = 1000000007L;
10void djikstra(int s){