理解题意后，实际上就是需要在这个图上选四个点 $a,b,c,d$，在两点之间走最短路的情况下，使得 $a->b->c->d$ 的路径之和最长。

很容易想到可以从每个点为起点求出任意两点的最短距离 $dis[i][j]$。

再枚举四个点 $a,b,c,d$ 求 $max(dis_{a,b}+dis_{b,c}+dis_{c,d})$ 即可。

这样的复杂度是 $O(n^4)$，显然只能通过 $40$ 分。

对于 $9 \sim 10$ 两个测试点，显然是完全图，那么答案即为 $3$。

综上可以获得 $50$ 分。

考虑如何优化：

这里我们可以发现，如果枚举 $a,b,c$，那么只需要找出离 $c$ 最远的 $d$ 即可，但是这里我们会发现，离 $c$ 最远的有可能是 $a,b$ 两个点，所以在极端情况下我们需要求出离 $c$ 最远的点 $f_c$，第二远的点 $g_c$，第三远的点 $h_c$，这样我们就可以直接找到最远的 $d$ 求得结果。

那么这样的复杂度是 $O(n^3)$，还需要优化。

这里我们可以发现不可能枚举 $a,b$ 然后找 $c,d$，但是我们可以枚举 $b,c$，然后从 $b$ 出发找 $a$，从 $c$ 出发找 $d$，方法同上。

但是这里要注意，从 $b$ 出发找 $a$ 有可能会影响 $c$ 出发找的 $d$，因为它们可能找到最远的是同一个点，所以不同找的顺序可能会影响答案。

那么这里我们需要讨论两种情况，先从 $b$ 找 $a$，再从 $c$ 找 $d$，以及先从 $c$ 找 $d$，再从 $b$ 找 $a$两种情况里求个最大值即可找到答案。

T3

本题有原题 S2022T1。

立方是送分的，考虑折半，枚举中间两个点 $j, k$。令 $i->j->k->l$。

则，贪心地，想到维护$d_{i}$为 $i$ 到非 $i$ 点的最大距离。

显然地，会有 形如 $i->j->k->i$ 的抽象情况（路径非法）。不难发现改为前三大后判断是否合法即可。

注意 ： $n=4000$,这题卡 $n^2 \log n$。不要带上不必要的 $\log$。