T5 午枫的双向奔赴 题目大意 给定一张图，小午和小枫分别在 111 号节点和 nnn 号节点，求出两人会和的最小时间，并且按照编号从小到大输出所有花费最小时间的节点 题解思路 设 d1id1_id1i 为从 111 号节点出发到达 iii 号节点的最短时间，dnidn_idni 为从 nnn 号节点出发到达 iii 号节点的最短时间。那么他们在 iii 号节点会和花费的时间为 max(d1i,dni)max(d1_i,dn_i)max(d1i ,dni ) 。所以他们会和的最短时间为 min⁡i=1n(max(d1i,dni))\min_{i=1}^{n} (max(d1_i,dn_i))mini=1n (max(d1i ,dni )) 。 分别以 111 号节点和 nnn 号节点为起始节点用 dijkstradijkstradijkstra 求出最短路，即 d1id1_id1i 和 dnidn_idni ，然后再求出他们会和需要的最短时间，最后找出所需最短时间的节点，按照编号从小到大输出。 参考代码

约定：从 uuu 走到 vvv 的最短路长度 LLL 记作 L=u→vL=u \rightarrow vL=u→v。 如果我们知道 L1=1→kL_1=1 \rightarrow kL1 =1→k 和 L2=n→kL_2=n \rightarrow kL2 =n→k，那么他们需要多长时间才能见面呢？显然，有一个人会先到，然后等待另一个人到。所以是 max⁡(L1,l2)\max(L_1,l_2)max(L1 ,l2 )。 如果我们对于所有的 kkk 都能知道 L1,L2L_1,L_2L1 ,L2 的话，就可以 O(n)O(n)O(n) 打擂台求出最短时间了。当然求出编号也不是难事，以后不再赘述。 很显然，L1L_1L1 可以跑一遍单源最短路，L2L_2L2 同样可以。 所以我们跑两遍单源最短路就行了！ 时间复杂度：O((n+m)log⁡m)O((n+m) \log m)O((n+m)logm) 空间复杂度：O(n+m)O(n+m)O(n+m) Code: