# CSES - Investigation

Authors: Andrew Wang, Chuyang Wang

## Table of Contents

ExplanationImplementation

## 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.util.*;import java.io.*;
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);		StringTokenizer st = new StringTokenizer(in.readLine());

### 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!