1928. 规定时间内到达终点的最小花费

1928. 规定时间内到达终点的最小花费

拆点+spfa

把点dist[x]拆成y个：dist[x][y]，第二维表示到x点的时间

const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
int e[N * 2], ne[N * 2], w[N * 2], h[N], idx;
int dist[N][N];
bool st[N][N];

void add(int a, int b, int c) {
  e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

class Solution {
 public:
  void init() {
    memset(h, -1, sizeof h);
    idx = 0;
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
  }
  int minCost(int m, vector<vector<int>>& edges, vector<int>& pf) {
    init();
    int n = pf.size();
    for (auto e : edges) {
      add(e[0], e[1], e[2]), add(e[1], e[0], e[2]);
    }

    queue<pair<int, int>> q;
    q.push({0, 0});
    st[0][0] = true;
    dist[0][0] = pf[0];

    while (q.size()) {
      auto u = q.front();
      q.pop();
      int x = u.first, y = u.second;
      st[x][y] = false;
      for (int i = h[x]; i != -1; i = ne[i]) {
        int nx = e[i], ny = y + w[i];
        if (ny > m) continue;
        if (dist[nx][ny] > dist[x][y] + pf[nx]) {
          dist[nx][ny] = dist[x][y] + pf[nx];
          if (!st[nx][ny]) {
            q.push({nx, ny});
            st[nx][ny] = true;
          }
        }
      }
    }
    int res = INF;
    for (int i = 0; i <= m; i++) res = min(res, dist[n - 1][i]);
    if (res == INF) return -1;
    return res;
  }
};