本题是一道稀疏图最短路问题。
我们可以把每个没有积水的交叉口看作一个顶点。大街和道路就是连接两个顶点的边，显然一个顶点最多与另外4个定点有边相连。 顶点数大约是250000， 边数大约是1000000,这个图是一个稀疏图。
稀疏图上的最短路是一个经典问题，可以用堆优化的Dijkstra或者SPFA。
本题是一道稀疏图最短路问题。
我们可以把每个没有积水的交叉口看作一个顶点。大街和道路就是连接两个顶点的边，显然一个顶点最多与另外4个定点有边相连。 顶点数大约是250000， 边数大约是1000000,这个图是一个稀疏图。
稀疏图上的最短路是一个经典问题，可以用堆优化的Dijkstra或者SPFA。
谢谢！