用c++数据结构来解决这个问题：给一个n (1≤n≤106) 个点m(1≤m≤106) 条边的无向图，求 s 到 t 的最短路的长度。 数据保证，s 出发可以到达 t。

这个问题可以使用 Dijkstra 算法来解决。Dijkstra 算法可以用于解决单源最短路径问题，即给定一个起点，求到其它所有点的最短路径。具体实现过程如下：

1. 初始化：将起点 s 的最短路径长度 dist[s] 设为 0，将其它点的最短路径长度 dist[i] 设为正无穷。

2. 将起点 s 加入到集合 S 中，表示已经找到了从起点 s 到 s 的最短路径。

3. 对于起点 s 相邻的点 i，更新其最短路径长度：

如果从起点 s 到 i 的路径长度 dist[s]+w(s,i) 小于 dist[i]，则更新 dist[i]=dist[s]+w(s,i)。

4. 从未加入集合 S 的点中选择一个距离起点 s 最近的点 u，将其加入集合 S 中。

5. 重复步骤 3 和 4，直到所有点都被加入集合 S 中，或者终点 t 被加入集合 S 中。

6. 返回 dist[t]，即起点 s 到终点 t 的最短路径长度。

这个算法可以用优先队列来实现，时间复杂度为 O(mlogn)，其中 m 是边数，n 是点数。

以下是 C++ 实现代码：

相关问题

用c++数据结构来解决这个问题，给出C++代码：给一个n (1≤n≤106) 个点m(1≤m≤106) 条边的无向图，求 s 到 t 的最短路的长度。 数据保证，s 出发可以到达 t。

这个问题可以使用 Dijkstra 算法来解决。以下是使用 C++ 实现的代码：

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

const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, w;
    Edge(int _v, int _w) : v(_v), w(_w) {}
};

vector<Edge> G[MAXN];
int dis[MAXN];
bool vis[MAXN];

void Dijkstra(int s) {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto e : G[u]) {
            int v = e.v, w = e.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Edge(v, w));
        G[v].push_back(Edge(u, w));
    }
    int s, t;
    cin >> s >> t;
    Dijkstra(s);
    cout << dis[t] << endl;
    return 0;
}

这段代码中，我们使用了一个优先队列来维护当前距离起点最近的点。每次从队列中取出距离最小的点，然后将这个点的所有出边加入队列中，更新到达这些点的最短距离。这个过程会一直持续到队列为空，所有点的最短距离都已经被确定。最后输出 s 到 t 的最短距离即可。

用c++数据结构来解决这个问题，不能使用stl容器，给出C++代码：给一个n (1≤n≤106) 个点m(1≤m≤106) 条边的无向图，求 s 到 t 的最短路的长度。 数据保证，s 出发可以到达 t。

好的，我们可以使用 Dijkstra 算法来解决这个问题。

Dijkstra 算法是一种贪心算法，用于解决带权重的单源最短路径问题。它的基本思想是从源节点开始，每次选择距离源节点最近的一个节点，然后以该节点为中心进行扩展，最终得到源节点到其他所有节点的最短路径。

以下是使用 C++ 实现 Dijkstra 算法的代码：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10; // 最大节点数
const int INF = 0x3f3f3f3f; // 无穷大

int n, m; // n个节点，m条边
int s, t; // 源节点s，目标节点t
int h[N], e[N], ne[N], w[N], idx; // 邻接表存储图
int dist[N]; // 存储源节点到各节点的最短距离
bool st[N]; // 存储节点是否已确定最短距离

void add(int a, int b, int c) // 添加一条边a->b，边权为c
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        st[t] = true;

        for (int j = h[t]; j != -1; j = ne[j])
        {
            int k = e[j];
            if (dist[t] + w[j] < dist[k])
                dist[k] = dist[t] + w[j];
        }
    }

    return dist[t]; // 返回源节点到目标节点的最短距离
}

int main()
{
    cin >> n >> m >> s >> t;

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

我们通过邻接表来存储图，`h[i]` 存储节点 `i` 的第一条边，`e[j]` 存储边 `j` 的目标节点，`w[j]` 存储边 `j` 的边权，`ne[j]` 存储边 `j` 的下一条边。在添加边的时候，因为是无向图，所以需要添加两条边。

在 Dijkstra 算法中，我们需要记录每个节点到源节点的最短距离，同时需要记录哪些节点已经确定了最短距离。我们使用 `dist` 数组来存储最短距离，使用 `st` 数组来存储节点是否已确定最短距离。在每次扩展时，我们选择距离源节点最近的一个节点进行扩展，然后更新与该节点相邻的节点的最短距离。最终得到的 `dist[t]` 即为源节点到目标节点的最短距离。

以上就是使用 C++ 实现 Dijkstra 算法求解单源最短路径问题的代码。