①极端数据
假设N=1000，M=20000，Q=20000
每个点的权值都一样大，并且图也是一般的无向图。
那么相当于就是一般的求最短路了。
做1000次spfa(); 复杂度就是 1000*O(spfa) 了.
spfa的复杂度是 kE.
因为是无向图,所以E=40000,假设k=2好了.那么总体复杂度就是
1000*(40000*2) = 8000W.
再加上询问复杂度: 20000*1000 = 2000W.

所以总体复杂度就是: 1E.
再加上边用__int64存的话复杂度会高一点.
那么一组这样的数据就要跑2S+了吧?
那么时限不是一般都是标程的5倍么?为什么时限才给5S么?
===============================================================
②另外还有,不对询问离线处理.直接对每个询问,枚举最高点.
for(i=1;i<=Q;i++) for(j=1;j<=n;j++)  == TLE.
for(i=1;i<=n;i++) for(j=1;j<=Q;j++)  == AC.
卡常数确实没有什么意义,只要算法对,我觉得应该要给AC.

• 看这个极端数据，那就是不让用djik预处理了。 (568) lijunle 2012-05-11 17:33:11