平凡的小白

题解

未归档(48)

/ 注册

全部文章 / 题解（共1篇）

【题解征集】牛客算法周周练5

D、小雨坐地铁思路：分层建图，求单源最短路。想到求最短路，不带负权边，很容易想到迪杰斯特拉算法，但是这并不是给你n个点m条边让你建好图再问你最短路，这里最难想到的就是怎么建图化为求最短路的一般情况。将每条地铁线看作一层图，因为每层之间可能公用了一些节点，所以我们对每个车站建立一个超级源点放...

Dijkstra

2020-05-06

1 659