仓库配送

[编程题]仓库配送

热度指数：1926 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

网易严选建有N个自营仓分布在全国各地，标记为仓库1到N。

给定一个配货时间组（v,u,w)，v为出发仓库，u为目标仓库，w为从出发仓库到目标仓库的耗时时间。可能存在仓库间过远，无法支持调拨转货。

指定一个出发仓库K，我们需要将供应商发送到K仓库的货配送到各个仓库。问配送到所有可到达仓库所要最短时间？如果无法全部调拨到，则返回-1.

进阶：时间复杂度 $O(m)\$ ，空间复杂度 $O(m)\$

输入描述:

第一行三个正整数，由空格分割，分别表示仓库个数N，出发仓K，以及配送时间组个数M
接下来 M行，每行三个整数，由空格分割，分别表示（v,u,w)三个数，v为出发仓库，u为目标仓库，w为从出发仓库到目标仓库的耗时时间
1<=N<=30
1<=K<=N
1<=M<=130
1<=u,v<=N
1<=w<=20

输出描述:

一行一个数字表示答案，配送到所有可达仓库到最短时间

示例1

输入

输出

说明


由图可知，所需最短时间为1+3+1=5

备注:

N的区间是[1, 100] ；
K的区间是[1, N] ；
times的最大长度是[1, 6000] ；
所有边 times[i] = (u, v, w)，1<=u, v <= N 0 <= w <= 100

算法知识视频讲解

小牛冲冲冲jiang

发表于 2021-09-16 10:44:33

动态规划相当于dp[i][j]代表从i到j的最短路径这时候的最短路径仅仅是初始化的时候点与点之间的直接相连。每次向其中增加一个中间节点所有节点指点的dp状态都会随之改变，即每增加一个节点所有的dp[i][j]都有可能更新但是不论增加的节点的顺序是什么，最终的结果都是一样的即增加 k1,k2 展开全文