# CSES - Investigation

Authors: Andrew Wang, Chuyang Wang

## Explanation

We can run Dijkstra keeping track of

- the distance: $\texttt{dist}[]$
- the number of ways with the minimum distance: $\texttt{num}[]$
- the minimum flights with the minimum distance: $\texttt{minf}[]$, and
- the maximum flights with the minimum distance: $\texttt{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 $\texttt{num}[u]$, $\texttt{minf}[u]$, and $\texttt{maxf}[u]$.

We also have to take into consideration if we can reach $u$ in an equivalent distance. If so, we update:

$\texttt{num}[u] = \texttt{num}[v] + \texttt{num}[u]$

$\texttt{minf}[u] = \min(\texttt{minf}[u], \texttt{minf}[v] + 1)$

$\texttt{maxf}[u] = \max(\texttt{maxf}[u], \texttt{maxf}[v] + 1)$

## Implementation

**Time Complexity:** $\mathcal{O}((N + M)\log N)$

C++

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN = 100001;const ll MAX = 0x3f3f3f3f3f3f3f3f;const int MOD = int(1e9) + 7;vector<pair<ll, int>> edge[MAXN];

Java

import java.io.*;import java.util.*;public class Investigation {static final int MOD = 1000000007;public static void main(String[] args) throws IOException {BufferedReader in =new BufferedReader(new InputStreamReader(System.in));PrintWriter out = new PrintWriter(System.out);

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!