1922: [Sdoi2010]大陆争霸

题目链接

题目大意：有向图求1到n的最短路。但是有些点在某些点被遍历之后才能走。

题解：设d1[x],d2[x]为城市x的到达时间，可进入时间。max(d1[x],d2[x])为真实的进入时间。d[x]记录城市x被多少个城市保护每次堆中取出一个真实进入时间最小的城市更新它所通往的城市的d1，保护城市的d2 保护城市的d–。若d=0，则可入堆复杂度(n+m)logn