思路
题意简化
* Marian 从节点 111 出发，Robin 从节点 nnn 出发
* 某些节点有马，骑上后边权永久减半
* 两人可以在任意节点等待对方
* 求最早相遇时间 = minvmax(d1(v), dn(v))\min_v \max(d_1(v),\; d_n(v))minv max(d1 (v),dn (v))
分层图 DIJKSTRA
每个人有两种状态：有马和无马。用 (节点,是否有马)(节点, 是否有马)(节点,是否有马) 建分层图。
状态定义：
* d[u][0]d[u][0]d[u][0]：到达节点 uuu，无马的最短时间
* d[u][1]d[u][1]d[u][1]：到达节点 uuu，有马的最短时间
转移规则：
从 (u,s)(u, s)(u,s) 经边 (u,v,w)(u, v, w)(u,v,w) 转移：
当前状态 → (v,0)(v, 0)(v,0) 无马 → (v,1)(v, 1)(v,1) 有马 s=0s = 0s=0（无马） d[u][0]+wd[u][0] + wd[u][0]+w 若 vvv 有马：d[u][0]+wd[u][0] + wd[u][0]+w s=1s = 1s=1（有马） — d[u][1]+w/2d[u][1] + w/2d[u][1]+w/2
骑马后状态不可逆（不会下马），所以 s=1s=1s=1 不会转移到 s=0s=0s=0。
代码
