补全：pair 里谁放前面

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

pair 比较时先比 first。下面的 Dijkstra 把 {点, 距离} 压进了堆，堆就按点的编号排了——在这张小图（0-1:10　0-2:1　1-2:1　1-3:1）上结果出错。补全堆的类型和压堆、弹堆的写法，输出距离表。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 补全：距离用 long long 为什么要求非负权 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
const ll INF = 1000000000;                       // 走不到的点记这个值，输出时写成 -1
using Graph = vector<vector<pair<int, int>>>;    // g[u] 里放 (邻居 v, 边权 w)

Graph build(int n, const vector<vector<int>>& edges) {
    // 无向图：每条边 {a, b, w} 两个方向都加；邻接表按邻居编号排好
    Graph g(n);
    for (const auto& e : edges) {
        g[e[0]].push_back({e[1], e[2]});
        g[e[1]].push_back({e[0], e[2]});
    }
    for (auto& adj : g) sort(adj.begin(), adj.end());
    return g;
}

string show(const vector<ll>& d) {
    // 距离表拼成 0/2/1/...，走不到的写 -1
    string s;
    for (size_t i = 0; i < d.size(); i++) {
        s += (i ? "/" : "") + (d[i] >= INF ? string("-1") : to_string(d[i]));
    }
    return s;
}

vector<ll> dijkstra(const Graph& g, int s) {
    vector<ll> d(g.size(), INF);
    vector<bool> done(g.size(), false);
    // 小根堆：greater 让距离小的先出（不写就是大根堆）
    priority_queue<pair<int, ll>, vector<pair<int, ll>>, greater<pair<int, ll>>> pq;   // TODO: 按距离排，距离放前面
    d[s] = 0;
    pq.push({s, 0});
    while (!pq.empty()) {
        auto [u, du] = pq.top();
        pq.pop();
        if (done[u]) continue;
        done[u] = true;
        for (auto [v, w] : g[u]) {
            if (du + w < d[v]) {
                d[v] = du + w;
                pq.push({v, d[v]});
            }
        }
    }
    return d;
}

int main() {
    Graph g = build(4, {{0, 1, 10}, {0, 2, 1}, {1, 2, 1}, {1, 3, 1}});
    cout << show(dijkstra(g, 0)) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

补全：pair 里谁放前面

更多题目

全部评论