建两张图,i->j 的有向边作为正图,j->i的逆边作为反图;这样正图一遍 dijistra 计算 1到其它点的最短路;反图一遍 dijistra 计算N到其它点的最短路; 每次的查询Q只用更新 d(1, i) + d(i, j) + d(j, N) 是否比 d(1, N) 短就行了
点赞 3

相关推荐

牛客网
牛客企业服务