DAY 4 下午

一些图论的知识（主要补充一下之前不了解的和比较重要）

竞赛图：完全图上的边加方向

仙人掌：每一条边至多属于一个环

 

 

 

前序：中左右

中序：左中右

后序：左右中

先加进去无向边

把每一个联通块看成一个大点

有向边一定是从一个连通块连向另一个连通块

在块内跑dijkstra

然后拓扑排序，入度为0的就跑dijkstra

怎么跑？

在一个连通块内，会有点的dis值被更新过，就把这些点压进堆里跑dijkstra（因为两个连通块是相连的，）

传递闭包

回答是否有路径可达

优化一下