[cf1051F]The shortest statement

Link

$n$个点,$m(m-n< 20)$条边的连通图,多组询问两点的最短路。

Solution

求出图的任意一个生成树,把不在生成树上的边所连接的点都做一遍最短路。
如果两点最短路在生成树上,那么求出树上最短路就得到答案。
否则,考虑floyd算法,选取点$u$,用$d[x][u]+d[u][y]$更新答案。选取的点$u$只需选取那些不在生成树上的边连接的点,因为如果生成树上的某点到点$x$在树上的距离不是最短路,那么最短路一定经过某个不在生成树上的边连接的点,因此只用这些点松弛就行了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注