最短路DP

$\text{score：0 + 0 + 0 = 0 rk：32/39}$ Problem A：最短路题面 题解该路径一定是从 $1$ 走到 $n$ 后，在从 $n$ 返回 $1$ 时在外围走一遭，再回到 $1 \rightarrow n$ 的路径走一段，再出去向 $1$ 走一段。。 设往外围走时的起点为 $a$ 类点，回到 $1 \rightarrow n$ 路径的点为 $b$ 类点，容易知道 $a$ 和 $b$ 交错出现才可能最优，那么整个图大概就这么个样（起点和终点不作标记） 令 $f_{i, j}$ 表示从 $1$ 走到 $i$，最后一个点为 $i$，为 $a$ 类点，倒数第二个点为 $j$，为 $b$ 类点 令 $g_{i, j}$ 表示从 $1$ 走到 $i$，最后一个点为 $i$，$i, j$ 都为 $b$ 类点 实际上 $f$ 可以直接转移，不需要 $g$，但这样复杂度时 $O (n^4)$ 的，故 $g$ 相当于辅助函数 用类似 $Dijkstra$ 的形式转移，设 $i$ 到 $j$ 的最短路径为 $d_{i, j}$（即使路径上所有点的 ...