标签-最小环

题意求无向图最小环,要求输出路径。其中点数 $N\le 100$题解本来求最小环挺简单的,恶心的就是这道题还要求输出路径。求最小环的方法就是用 $spfa$ 跑最短路,得到最初的距离 $dis[u][v]$ 和最短路 $mn[u][v]$ 。那么对于每个节点 $x$ ,它与 $u$ 和 $v$ 相邻,那么他们最小环的长度即为:$$mn[u][v]+dis[x][u]+dis[x][v]$$每...
   题解    0 条评论