这个问题本质上是一个最短路径问题，我们可以把每个数字看作图中的一个节点，序列的生成规则就是图中的边。

图的构建 节点：数字1到n

边有两种类型：

递增边：从数字u到u+1，边的权重是w[u+1]

乘法边：从数字u和v到u×v，边的权重是w[u×v]

算法选择 由于所有权重都是正数，我们使用Dijkstra算法来求解单源最短路径：

起点：数字1（因为所有序列都必须从1开始）

初始距离：dist[1] = w[1]（因为包含1的最简单序列就是[1]本身）

算法过程：使用优先队列，每次取出当前距离最小的数字，然后用它来更新通过递增和乘法规则能够到达的其他数字的距离

算法步骤 初始化距离数组，除了dist[1] = w[1]外，其他都设为无穷大

创建优先队列，将数字1及其距离w[1]加入队列

当队列不为空时：

取出当前距离最小的数字u

如果u+1不超过n，尝试用dist[u] + w[u+1]更新dist[u+1]

对于所有满足u×v不超过n的数字v，尝试用dist[u] + w[u×v]更新dist[u×v]

如果更新成功，将相应的数字加入优先队列

最终dist[1..n]就是要求的s[1..n]