hiho一下第185周《积水的城市》题目分析

1
0

本题是一道稀疏图最短路问题。

我们可以把每个没有积水的交叉口看作一个顶点。大街和道路就是连接两个顶点的边,显然一个顶点最多与另外4个定点有边相连。 顶点数大约是250000, 边数大约是1000000,这个图是一个稀疏图。

稀疏图上的最短路是一个经典问题,可以用堆优化的Dijkstra或者SPFA。

大家可以参考 https://hihocoder.com/problemset/problem/1093

3 answer(s)

2

优先队列的BFS过了,但觉得哪里怪怪的=_=

  • 代码可以看看吗。用了DFS,果然超时了。

  • 每周比赛结束之后可以看别人的代码

  • 添加评论
  • reply
0

有什么trick么 一直只有90分~~!

0

上面90分的同学试试这个数据:

4 5
100 4 1
3 3 3 2
2
2 3
3 2
1
2 2 2 4

write answer 切换为英文 切换为中文


转发分享