美团2018校招真题题解 搜索 分层图最短路 前缀和（更新ing

病毒传播
思路：应该是比较简单的一道题，因为点数是千数量级的，floyd肯定不行了，看到边数也是1000，这就暗示了要从边下手，直接bfs找每个S集合内的点到各点的最短路这就是O(n*m)，S不连通则无满足点，否则寻找S集合内满足以下条件的点： 思路：应该是比较简单的一道题，因为点数是千数量级的，floyd肯定不行了，看到边数也是10