CSES - Investigation

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:

Implementation

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

Copy
#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];

Copy
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);
		StringTokenizer st = new StringTokenizer(in.readLine());