C++ – 图与最短路

struct group_t {
    struct edge_t {
        lli u;
        lli v;
        lli w;
        lli nxt;
    };

    lli n;
    vector<lli> head;
    vector<edge_t> edge;

    group_t(lli n) : n(n), head(n + 1, -1), edge(1) { }

    void add_edge(lli u, lli v, lli w) {
        edge.push_back({ u, v, w, head[u] });
        head[u] = edge.size() - 1;
    }

    void col_dis(lli s, vector<lli>& dis, vector<lli>* pat = nullptr) {
        vector<bool> vis(head.size(), false);
        dis.clear();
        dis.resize(head.size(), inf);
        if (pat != nullptr) pat->clear();
        if (pat != nullptr) pat->resize(head.size(), -1);
        queue<lli> q;
        dis[s] = 0;
        vis[s] = true;
        q.push(s);
        while (!q.empty()) {
            lli u = q.front();
            q.pop();
            for (lli i = head[u]; ~i; i = edge[i].nxt) {
                auto [_1, v, w, _2] = edge[i];
                if (vis[v]) continue;
                vis[v] = true;
                dis[v] = dis[u] + w;
                if (pat != nullptr) (*pat)[v] = u;
                q.push(v);
            }
        }
    }

    struct disn_t {
        lli v;
        lli w;
        friend bool operator<(const disn_t& a, const disn_t& b) { return a.w > b.w; }
    };

    void col_dij(lli s, vector<lli>& dis, vector<lli>* pat = nullptr) {
        vector<bool> vis(head.size(), false);
        dis.clear();
        dis.resize(head.size(), inf);
        if (pat != nullptr) pat->clear();
        if (pat != nullptr) pat->resize(head.size(), -1);
        priority_queue<disn_t> q;
        dis[s] = 0;
        q.push({ s, 0 });
        while (!q.empty()) {
            lli u = q.top().v;
            q.pop();
            if (vis[u]) continue;
            vis[u] = true;
            for (lli i = head[u]; ~i; i = edge[i].nxt) {
                auto [_1, v, w, _2] = edge[i];
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    if (pat != nullptr) (*pat)[v] = u;
                    q.push({ v, dis[v] });
                }
            }
        }
    }
};