快速公交

/*
 * Problem: Xiao Kou plans to go to the Autumn City Market. Due to the crowd, his walking speed is affected:
 * - Moving from station x to station x + 1 costs 'inc' time.
 * - Moving from station x to station x - 1 costs 'dec' time.
 * There are 'm' buses, numbered from 0 to m-1. Xiao Kou can take bus i to move from station x to station jump[i]*x at the cost of cost[i].
 * Xiao Kou can take any bus any number of times. The start station is 0 and the target station is 'target'.
 * Return the minimum time Xiao Kou needs to reach the target station, modulo 1000000007 (1e9 + 7).
 * Note: Xiao Kou can reach a station number greater than 'target' during the process.
 */

import java.util.*;
import java.util.stream.Stream;

public class MinTimeToTargetStream {
    public int minCost(int target, int inc, int dec, int[] jump, int[] cost) {
        long mod = 1000000007;
        Map<Long, Long> dp = new HashMap<>();
        dp.put(0L, 0L);
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
        pq.add(new long[]{0, 0});

        while (!pq.isEmpty()) {
            long[] curr = pq.poll();
            long pos = curr[0], time = curr[1];
            if (pos == target) return (int)(time % mod);

            if (dp.getOrDefault(pos, Long.MAX_VALUE) < time) continue;

            Stream.of(new long[]{pos + 1, time + inc},
                      pos > 0 ? new long[]{pos - 1, time + dec} : null)
                  .filter(Objects::nonNull)
                  .forEach(next -> {
                      if (!dp.containsKey(next[0]) || dp.get(next[0]) > next[1]) {
                          dp.put(next[0], next[1]);
                          pq.add(next);
                      }
                  });

            for (int i = 0; i < jump.length; i++) {
                long newPos = pos * jump[i];
                if (!dp.containsKey(newPos) || dp.get(newPos) > time + cost[i]) {
                    dp.put(newPos, time + cost[i]);
                    pq.add(new long[]{newPos, time + cost[i]});
                }
            }
        }
        return -1;
    }
}