给一个 � ( 1 ≤ � ≤ 1 0 6 ) n(1≤n≤10 6 ) 个点 � ( 1 ≤ � ≤ 1 0 6 ) m(1≤m≤10 6 ) 条边的无向图，求 � s 到 � t 的最短路的长度。 数据保证， � s 出发可以到达 � t。

可以使用 Dijkstra 算法或者 A* 算法求解。对于 Dijkstra 算法，可以使用堆优化来加速，时间复杂度为 $O(m\log n)$，其中 $m$ 是边数，$n$ 是点数。对于 A* 算法，需要指定一个启发式函数来估计从当前点到终点的距离，时间复杂度为 $O(m)$ 到 $O(m\log n)$ 不等，具体取决于启发式函数的好坏。下面是使用 Dijkstra 算法的代码实现：

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

const int MAXN = 1000000;
const int INF = 0x3f3f3f3f;
struct Edge {
    int to;
    int w;
    int next;
} edges[MAXN];
int head[MAXN];
int cnt = 0;
int n, m;
int dis[MAXN];
bool vis[MAXN];

void addEdge(int u, int v, int w) {
    edges[cnt].to = v;
    edges[cnt].w = w;
    edges[cnt].next = head[u];
    head[u] = cnt++;
}

void dijkstra(int start, int end) {
    memset(vis, false, sizeof(bool) * (n+1));
    memset(dis, INF, sizeof(int) * (n+1));
    dis[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int k = head[u]; k != -1; k = edges[k].next) {
            int v = edges[k].to;
            if (dis[v] > dis[u] + edges[k].w) {
                dis[v] = dis[u] + edges[k].w;
                pq.push(make_pair(dis[v], v));
            }
        }
    }
}

int main() {
    int start, end;
    memset(head, -1, sizeof(head));
    cin >> n >> m >> start >> end;
    if (n == 0) {
        cout << "No path" << endl;
        return 0;
    }
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    dijkstra(start, end);
    cout << dis[end] << endl;
    return 0;
}

其中使用了 STL 中的优先队列实现堆优化。