vector<vector<pair<int,int>>> 详解（Dijkstra）

一、概念与用途

• pair<int,int>：存放两个整数，常用来表示图中的边 (目标节点, 权重) 或二维坐标 (x,y)。

• vector<pair<int,int>>：一维动态数组，存放若干 pair<int,int>。

• vector<vector<pair<int,int>>>：二维动态数组，外层 vector 表示节点集合，内层 vector 表示该节点对应的边或坐标集合。

常见应用：

• 图的邻接表存储结构（尤其是带权图）；

• 分组后的键值对集合；

• 二维表格数据结构。

三、初始化与常见构造方式

#include <vector>
#include <utility>

// 空的外层 vector
std::vector<std::vector<std::pair<int,int>>> vv;

// 预设外层大小 n，每个内层为空
std::vector<std::vector<std::pair<int,int>>> vv2(n);

// 直接构造一个 2x3 的二维结构，元素初始为 (0,0)
std::vector<std::vector<std::pair<int,int>>> vv3(
    2, std::vector<std::pair<int,int>>(3, std::make_pair(0,0))
);

四、插入元素

在 GCC 4.9.2 中，推荐直接使用：

vv[u].push_back(std::make_pair(v, w));

这种写法兼容性最佳，也避免了 emplace_back 的使用。

五、遍历方式（）

1. 索引遍历：

for (size_t u = 0; u < vv.size(); ++u) {
    for (size_t i = 0; i < vv[u].size(); ++i) {
        int to = vv[u][i].first;
        int wt = vv[u][i].second;
    }
}

1. 迭代器遍历：

for (std::vector<std::vector<std::pair<int,int>>>::iterator it = vv.begin(); it != vv.end(); ++it) {
    for (std::vector<std::pair<int,int>>::iterator jt = it->begin(); jt != it->end(); ++jt) {
        int to = jt->first;
        int wt = jt->second;
    }
}

六、示例：加权图邻接表

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int> > > adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(std::make_pair(v, w));
        // 若为无向图：
        // adj[v].push_back(std::make_pair(u, w));
    }

    for (int u = 1; u <= n; ++u) {
        cout << u << ":";
        for (size_t i = 0; i < adj[u].size(); ++i) {
            cout << " (" << adj[u][i].first << "," << adj[u][i].second << ")";
        }
        cout << '\n';
    }
    return 0;
}

七、Dijkstra 算法实现

#include <bits/stdc++.h>
using namespace std;

vector<int> dijkstra(int n, int src, const vector<vector<pair<int,int> > > &adj) {
    const int INF = 1000000000;
    vector<int> dist(n + 1, INF);
    dist[src] = 0;

    typedef pair<int,int> PII;
    priority_queue<PII, vector<PII>, greater<PII> > pq;
    pq.push(make_pair(0, src));

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, s;
    cin >> n >> m >> s;

    vector<vector<pair<int,int> > > adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(std::make_pair(v, w));
        // 若为无向图：
        // adj[v].push_back(std::make_pair(u, w));
    }

    vector<int> dist = dijkstra(n, s, adj);

    for (int i = 1; i <= n; ++i) {
        if (dist[i] == 1000000000) cout << "INF ";
        else cout << dist[i] << " ";
    }
    cout << "\n";

    return 0;
}

八、输入输出示例

输入：

5 6 1
1 2 2
1 3 5
2 3 1
2 4 2
3 5 3
4 5 1

输出：

0 2 3 4 5

九、总结

1. vector<vector<pair<int,int>>> 是带权邻接表的经典表示方式，外层为节点，内层为边集合 (目标, 权重)。

2. 使用 push_back 即可实现插入，若需要优化性能，可以结合 reserve() 提前分配内存，减少扩容次数。

3. Dijkstra 算法基于该结构运行高效，适合稀疏图的最短路径求解。

注意：priority_queue<PII, vector<PII>, greater<PII>> pq; 的作用？

它是让 C++ STL 默认的大根堆变成小根堆，用于 Dijkstra 算法找最短距离。
如果不想写这种复杂的模板参数，有几种替代方案：

方案一：用 自定义结构体 + 重载 <

默认的 priority_queue 是大根堆，如果把比较逻辑改成“距离小的优先”，也能实现小根堆。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int dist, id;
    bool operator<(const Node &other) const {
        return dist > other.dist;  
        // 注意这里写成 > ，这样距离小的会排在堆顶
    }
};

vector<int> dijkstra(int n, int src, const vector<vector<pair<int,int>>> &adj) {
    const int INF = 1000000000;
    vector<int> dist(n + 1, INF);
    dist[src] = 0;

    priority_queue<Node> pq;
    pq.push((Node){0, src});

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        int u = cur.id;
        if (cur.dist > dist[u]) continue;

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push((Node){dist[v], v});
            }
        }
    }
    return dist;
}

优点：代码更直观，不需要写 greater<PII>。
缺点：需要多写一个结构体。

方案二：直接用 set<pair<int,int>>

利用 set 的自动排序特性（按 pair.first 升序），可以不用 priority_queue。
但要注意：更新时必须删除旧的 (dist[v], v) 再插入新的 (dist[v], v)，否则会有重复。

vector<int> dijkstra(int n, int src, const vector<vector<pair<int,int>>> &adj) {
    const int INF = 1000000000;
    vector<int> dist(n + 1, INF);
    dist[src] = 0;

    set<pair<int,int>> st;
    st.insert(make_pair(0, src));

    while (!st.empty()) {
        pair<int,int> cur = *st.begin();
        st.erase(st.begin());
        int u = cur.second;

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if (dist[u] + w < dist[v]) {
                if (dist[v] != INF) {
                    st.erase(make_pair(dist[v], v)); // 删除旧的
                }
                dist[v] = dist[u] + w;
                st.insert(make_pair(dist[v], v));   // 插入新的
            }
        }
    }
    return dist;
}

优点：不用写自定义比较器，set 会自动维护最小距离。
缺点：常数时间比 priority_queue 大，运行稍慢。

方案三：朴素 Dijkstra（不用堆）

适用于 稠密图（边接近 n^2），直接每次扫描所有点找最小的未访问点，复杂度 O(n^2)。

vector<int> dijkstra(int n, int src, const vector<vector<pair<int,int>>> &adj) {
    const int INF = 1000000000;
    vector<int> dist(n + 1, INF);
    vector<bool> vis(n + 1, false);
    dist[src] = 0;

    for (int i = 1; i <= n; ++i) {
        int u = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        if (u == -1 || dist[u] == INF) break;
        vis[u] = true;

        for (size_t k = 0; k < adj[u].size(); ++k) {
            int v = adj[u][k].first;
            int w = adj[u][k].second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    return dist;
}

优点：最简单，不依赖 priority_queue、set。
缺点：复杂度高，稀疏图性能差。

总结

• 最快、常用 → priority_queue（推荐 方案一：自定义结构体，直观易懂）。

• 更简洁 → set。

• 稠密图 或者 小规模数据 → 朴素 Dijkstra。