CSES - Investigation

Authors: Andrew Wang, Chuyang Wang

Table of Contents

ExplanationImplementation

Explanation

We can run Dijkstra keeping track of

  • the distance: dist[]\texttt{dist}[]
  • the number of ways with the minimum distance: num[]\texttt{num}[]
  • the minimum flights with the minimum distance: minf[]\texttt{minf}[], and
  • the maximum flights with the minimum distance: maxf[]\texttt{maxf}[].

For every node, vv, we take into consideration all of its neighbors, uu. If we can reach uu in a shorter distance than its current minimum, we update the distance and reset num[u]\texttt{num}[u], minf[u]\texttt{minf}[u], and maxf[u]\texttt{maxf}[u].

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

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

Implementation

Time Complexity: O((N+M)logN)\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!