给出有向图的点数\(n\)和邻接矩阵\(G\), 求\[P=∑_{1≤x,y,z≤n,x≠y,y≠z}d(x,y,z)\] 其中\(d(x,y,z)\)表示从\(x\)不经过\(y\)到\(z\)的最短路,如果无法到达则为\(-1\)

\[4≤n≤300,−1≤G_{i,j}≤10000,G_{i,i}=0\]

首先你要知道\(floyed\)的本质是枚举中转点。

那么不经过\(y\)点的最短路矩阵相当于使用除\(y\)以外的点作为中转点更新后的邻接矩阵

于是考虑分治,递归到\(l==r\)时仅有节点\(l\)未被作为中转点 那么在做到\([l,r]\)时，使用\([l,mid]\)更新\([mid+1,r]\)，使用\([mid+1,r]\)更新\([l,mid]\)即可。