所谓的做N次最短路就是枚举每个店作为最高消费的点，
然后做单源最短路，求出这个点到其他点最短路，但是不能
经过比其消费更高的顶点。
    之后在查询的时候依次假设每个点作为最高消费点，然
后把两部分最短路以及这个点的消费加起来去更新结果，这
样查询就是O(NQ)的复杂度。
    但需要注意的是，假定我们用f[i][j]记录了以i为最高
消费点到j这个点的最短路，如果查询时两重循环先是for(i=0;i<Q;i++)
然后for(j=1;j<=N;j++)这样大概会TLE，但如果先将查询读
入，然后用for(i=1;i<=N;i++)for(j=0;j<Q;j++)这样做的话
就应该可以AC了，这个貌似是属于底层优化的范畴吧，就好
比for(i)for(j)去遍历f[i][j]与for(j)for(i)遍历f[i][j]
的效率是不一样的。

• Re:做N次最短路，然后O(NQ)查询需要注意的地方 (10) shahdza 2012-05-10 10:13:46
  • 呃，不过说起来，这个题貌似还可以卡空间，因为后来想通了，其实可以不用二维数组 (65) 0909100811 2012-05-10 15:19:56