Video Solution

By David Zhou

Explanation

Let's consider a simpler problem: given a graph, find the shortest cycle that passes through node 1.

What does a cycle through node 1 look like? In any cycle through node 1, there exists two nodes $u$ and $v$ on that cycle such that there is a path from 1 to $u$ and 1 to $v$, and there is an edge between $u$ and $v$. The length of this cycle is $dist(1, u) + dist(1, v) + 1$.

One might now try to use BFS to find $dist(1, i)$ for each $i$ in $\mathcal{O}(N + M)$ time and then check for each edge $(u, v)$ whether $dist(1, u) + dist(1, v) + 1$ is minimal.

Of course, this means that we might count a "cycle" like $1 \rightarrow x \rightarrow u \rightarrow v \rightarrow x \rightarrow 1$. However, this doesn't matter for our original problem, since the shortest cycle will always be shorter than such a "cycle".

There's one problem with this approach though: if the edge $(u, v)$ is on the path from node 1 to node $v$, then $1 \rightarrow u \rightarrow v \rightarrow 1$ isn't a cycle! And this time, it does matter in our original problem!

Fortunately, there's a relatively simple fix.

Instead of first finding all $dist(1, i)$ and then checking for the minimum, do both at the same time during the BFS.

Now to prevent "backtracking", we only consider $dist(1, u) + dist(1, v) + 1$ as a minimum if we're currently at node $u$ and $dist(1, u) \leq dist(1, v)$.

This algorithm runs in $\mathcal{O}(N + M)$ time. Since $N$ and $M$ are so small, we can just apply this algorithm for all nodes instead of just node 1.

The final complexity of this solution is thus $\mathcal{O}(N(N + M))$.

Implementation

Copy
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 2510;
const int inf = 1000000007;

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!

using pi = pair<int, int>;
using pl = pair<ll, ll>;