Dijkstra + Heap，TLE 25pts

rt，代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <queue>
using namespace std;
const int N = 2 * 1e6 + 10;

long long h[N], nxt[5 * N], vtx[5 * N], w[N], idx;
long long rh[N], rnxt[5 * N], rvtx[5 * N], rw[N], ridx;
int n, m, dist[N], vis[N];
long long ans;

struct edge {
    int u, v, w;

    friend bool operator < (edge x, edge y) {
        return x.w > y.w;
    }
};

priority_queue <edge> q;

void addEdge(long long u, long long v, long long weight) {
    int p = h[u], found = 0;
    while (p != -1) {
        if (vtx[p] == v) {
            found = 1, w[p] = min(w[p], weight);
        }
        p = nxt[p];
    }
    if (!found) {
        vtx[idx] = v, nxt[idx] = h[u], w[idx] = weight, h[u] = idx++;
    }
    p = rh[u], found = 0;
    while (p != -1) {
        if (rvtx[p] == u) {
            found = 1, rw[p] = min(rw[p], weight);
        }
        p = rnxt[p];
    }
    if (!found) {
        rvtx[ridx] = u, rnxt[ridx] = rh[v], rw[ridx] = weight, rh[v] = ridx++;
    }
}

void dijkstra(int u) {
    dist[u] = 0;
    edge tEdge;
    tEdge.u = u, tEdge.v = u, tEdge.w = 0;
    q.push(tEdge);
    while (!q.empty()) {
        tEdge = q.top();
        q.pop();
        int tmp = tEdge.v;
        if (vis[tmp]) continue;
        vis[tmp] = 1;
        int p = h[tmp];
        while (p != -1) {
            if (!vis[vtx[p]] && dist[tmp] + w[p] < dist[vtx[p]]) {
                dist[vtx[p]] = dist[tmp] + w[p];
                tEdge.u = tmp, tEdge.v = vtx[p], tEdge.w = dist[tmp];
                q.push(tEdge);
            }
            p = nxt[p];
        }
    }
}

void r_dijkstra(int u) {
    dist[u] = 0;
    edge tEdge;
    tEdge.u = u, tEdge.v = u, tEdge.w = 0;
    q.push(tEdge);
    while (!q.empty()) {
        tEdge = q.top();
        q.pop();
        int tmp = tEdge.v;
        if (vis[tmp]) continue;
        vis[tmp] = 1;
        int p = rh[tmp];
        while (p != -1) {
            if (!vis[rvtx[p]] && dist[tmp] + rw[p] < dist[rvtx[p]]) {
                dist[rvtx[p]] = dist[tmp] + rw[p];
                tEdge.u = tmp, tEdge.v = rvtx[p], tEdge.w = dist[tmp];
                q.push(tEdge);
            }
            p = rnxt[p];
        }
    }
}

int main() {
    memset(h, -1, sizeof(h));
    memset(dist, 0x3f, sizeof(dist));
    memset(rh, -1, sizeof(rh));
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        if (x != y) addEdge(x, y, z); 
    }
    dijkstra(1);
    for (int i = 1; i <= n; i++) ans += dist[i];
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    while (!q.empty()) q.pop();
    r_dijkstra(1);
    for (int i = 1; i <= n; i++) ans += dist[i];
    cout << ans << endl;
    return 0;
}

谢谢各位大佬！！