再次踩坑
三个小时没了 。。。。。。。。。。。。。
我想的前面的思路和y总的差不多,后面的就有点走捷径了。现在明白一个道理,姜还是老的辣,你y总就是你y总。
我在做拓扑序的时候,直接让第一起点为s点所在的联通快,然后直接做,果然wa了
后来想了想 假如下图的方式那么肯定要错呀。
像这样的话 第四个点直接更新不了了。
每次做dijkstra的时候 要把id = x的所有点都加进堆 为什么?
因为不这样做的话 假如这个联通快里面的所有点距离都是INF那么这个呃呃呃联通快连接的航线就不会被更新了
还有就是判断这个点是不是在下一个联通快中 不能放在
if(dist[j] > dist[t] + w[i] )
里面判断为什么?
因为如果这个点所有距离为INF或者另一个联通块的值很大那么更新不了,所以要放在外面。
还有初始化dist的要放在topsort里面 还有st函数 不用每次清零 因为只会遍历一次。
细节太多要细心认真QAQ