有个城市被一条河分成了南北两部分, 它们之间有N+1个航道, 标记为0~N, 每个航道的两端是一个码头, 然后每个码头都只属于一个航道, 航道间也不交叉. 现在给出各
航道的航行时间以及同一河岸上各码头间的行走时间, 求出从起点S出发到终点T所需的最短时间.
     刚开始以为是简单的最短路题, 只要对码头编号进行一定的处理后就可以建图. 然后突然发现顶点数多达100W, 这样无论是邻接矩阵还是邻接表都是很难把图建出来的,
 虽然内存给了128M. 后来想到了用时间换取空间的方法, 即不把图显式地建出来, 而是在Dijkstra里每次扩展节点的时候根据节点的编号信息对它的下一个节点进行扩展, 
一共有6种点:
①点在北岸且不是左右端点, 则它可以往左, 右走, 或通过航道去南岸;
②点在南岸且不是左右端点, 则它可以往左, 右走, 或通过航道去北岸;
③点是北岸左端点, 则它可以往右走, 或通过航道去南岸;
④点是北岸右端点, 则它可以往左走, 或通过航道去南岸;
⑤点是南岸左端点, 则它可以往右走, 或通过航道去北岸;
⑥点是南岸右端点, 则它可以往左走, 或通过航道去北岸;
这样扩展的话就不用事先建图了, 省去了大量的空间;
然后由于__int64的操作速度实在是太慢了, 开了dis[v]记录节点当前最短距离后, 内存增加了一倍, 速度反而木有得到优化;
加dis[]: 28332K 110MS;
不加dis[]: 12680K 110MS:
要代码的站内m我吧.

• Re:题意+用Dijkstra做的思路 110MS (699) BYQX 2018-09-22 21:39:59