P2446 [SDOI2010] 大陆争霸
这个昨天晚上🍠里找到的。
之前不是写了 拓扑排序 嘛，然后就想着把这个也写了。
我是区。
题意很简单，就是 dij ，但是可以发现我们到一个点不能直接进去，所以我们的最短时间是
max(最短路时间，所有结节发生器都坏掉的最晚时间)max(最短路时间，所有结节发生器都坏掉的最晚时间)max(最短路时间，所有结节发生器都坏掉的最晚时间)
那开两个来存就好了。
对于任意点 uuu ，我们的结节破坏时间其实是最晚一个结节发生器被炸掉的时间，所以可以记作 lim[u]lim[u]lim[u] ，然后最短路走到的就是 dis[u]dis[u]dis[u] ，所以我们刚刚的公式就是 time[u]=max(dis[u],lim[u])time[u] = max(dis[u],lim[u])time[u]=max(dis[u],lim[u]) 。
我们搞两个存图的，一个用来跑最短路，一个跑 limlimlim ，但是跑 limlimlim 的是反图，因为我前面的点 ppp 被炸掉了我的点 uuu 才会少一个限制，我们搞一个 ininin 数组来存每个点 uuu 还要炸掉的结节发生器数量，每当 ppp 被炸掉了，就跑一次与 ppp 直接相连的点把它们的 ininin 值都减一，如果 in[u]=0in[u]=0in[u]=0 ，那这个点就可以被放进优先队列里走最短路。
所以这题是 dij + 拓扑。
拓扑只是用了它入度的思想，其实就是我们的 ininin 数组。
青++。
assignassignassign 就是把 vector 清空再赋值，不会的同学可以了解一下。
