RT,对于那个建正反图跑两次 Dijkstra 的做法,只用边更新而不用点更新也能 AC ,那么只用边更新是对的吗?/yiw
for (int i = 1; i <= m; ++ i)
if (frm[oes[i].u] != gto[oes[i].v])
ans = std::min(ans, f[oes[i].u] + weight[i] + g[oes[i].v]);
for (int i = 1; i <= n; ++ i)
if (frm[i] != gto[i])
ans = std::min(ans, f[i] + g[i]);