在牛客上看了很多面经~来此回馈一波 一、微软STCA 1.笔试1/21 笔试三道题目，一共120分钟，没有摄像头和录音，提交后不会给结果反馈你有没有对。 （1）简单模拟，记不太得了，很简单。 （2）机器人扫地，leetcode题目（貌似要会员），大概意思是说给你一个矩阵表示一个矩形的房间，矩阵值为0或者1，0表示没有障碍物，1表示有障碍物。此刻有一个机器人起始在左上角的格子，方向向右开始打扫，当机器人碰到障碍物时，他会顺时针旋转一个方向（比如向右->向下）继续进行打扫，问机器人可以打扫多少块格子？（我是dfs+dp） （3）有n个小镇，有m条路将n个...

微软的笔试：有n个小镇，有m条路将n个小镇连接起来，n个小镇中，有k个小镇设置有医院，问其他小镇到最近的医院要多久？ 我当时直接以每个医院作为源点，做了k次dijkstra，有没有时间复杂度更小的算法啊？总感觉会超时，忘记数据范围是多少了。菜鸡提问，求各位大佬康康~