讨论一道最短路径问题

最近碰到一道题，不知道该用什么方法做比较好。
有一个n个点条边的无向图，其中k个点是加油站。现在需要求出n个点中每个点来说距
离最近的一个加油站的距离。若这个点是加油站，那么最短距离就是0。数据保证每个
点都能至少到达一个加油站。没有负边或者环。

我尝试的方法是对于k个加油站每个加油站用一个Dijkstra算法求这个加油站到其它点
的最短距离，然后对于每个点来说比较k个最短距离求出真正的最短距离。但时间复杂
度太高了。想问一下大家有什么好的想法吗，谢谢

还是研究一下最短送货途径吧。 亚马逊有算法，给派送人员事先规划了最短途径。 是送几十个包裹的最短途径。还要考虑道路的堵塞情况。 估计每条道路都有堵塞加权。

就是用最短时间送最多的包裹。 有道路长度因素，还有时间因素

这不是那个谷仓问题吗， divid and conquer

感觉用两个数列加一次宽度优先搜索就行
两个数列等长于节点数，一个数列保留每个节点距离最近的加油站编号，第二个数列保留离那个加油站的距离，初始化所有距离无穷大，宽度优先相当于动态规划，每一部都更新所有阶段的距离
复杂度O(边数x节点数)

【 在 hangzhouxi () 的大作中提到: 】
: 最近碰到一道题，不知道该用什么方法做比较好。
: 有一个n个点条边的无向图，其中k个点是加油站。现在需要求出n个点中每个点来说距
: 离最近的一个加油站的距离。若这个点是加油站，那么最短距离就是0。数据保证每个
: 点都能至少到达一个加油站。没有负边或者环。
: 我尝试的方法是对于k个加油站每个加油站用一个Dijkstra算法求这个加油站到其它点
: 的最短距离，然后对于每个点来说比较k个最短距离求出真正的最短距离。但时间复杂
: 度太高了。想问一下大家有什么好的想法吗，谢谢