dijkstra

lc3928

跑2n次dijk+剪枝优化

class Solution {
vector<int> dijkstra(vector<vector<pair<int, int>>>& g, int start, int price) {
vector<int> dis(g.size(), price);
// 堆中保存 (起点到节点 x 的最短路长度，节点 x)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dis[start] = 0; // 起点到自己的距离是 0
pq.emplace(0, start);

while (!pq.empty()) {
auto [dis_x, x] = pq.top();
pq.pop();
if (dis_x > dis[x]) {
// x 之前出堆过
continue;
}
for (auto& [y, wt] : g[x]) {
auto new_dis_y = dis_x + wt;
if (new_dis_y < dis[y]) {
dis[y] = new_dis_y;
// 更新 x 的邻居的最短路
// 懒更新堆：只插入数据，不更新堆中数据
// 相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue
pq.emplace(new_dis_y, y);
}
}
}

return dis;
}

public:
vector<int> minCost(int n, vector<int>& prices, vector<vector<int>>& roads) {
int max_price = ranges::max(prices);

vector<vector<pair<int, int>>> g1(n);
vector<vector<pair<int, int>>> g2(n);
for (auto& e : roads) {
int x = e[0], y = e[1], cost = e[2], tax = e[3];
if (cost < max_price) {
g1[x].emplace_back(y, cost);
g1[y].emplace_back(x, cost);
}
if (1LL * cost * tax < max_price) {
g2[x].emplace_back(y, cost * tax);
g2[y].emplace_back(x, cost * tax);
}
}

vector<int> ans(n, INT_MAX);
for (int i = 0; i < n; i++) {
vector<int> dis1 = dijkstra(g1, i, prices[i]);
vector<int> dis2 = dijkstra(g2, i, prices[i]);
for (int j = 0; j < n; j++) {
if (dis1[j] + dis2[j] < ans[i] - prices[j]) { // 为避免加法溢出，把 prices[j] 移到右边
ans[i] = prices[j] + dis1[j] + dis2[j];
}
}
}
return ans;
}
};