dijkstra代码：

#include <bits/stdc++.h>

using namespace std;
int n, m;
long long ans;
vector<vector<pair<int, int>>> e, g;
bitset<1000032> vis;
int dis[1000005];

struct cmp {
    bool operator()(int a, int b) {
        return dis[a] > dis[b];
    }
};

priority_queue<int, vector<int>, cmp> q;

void dijkstra(vector<vector<pair<int, int>>> a) {
    vis.reset();
    memset(dis, 0x7f, sizeof(dis));
    dis[1] = 0;
    q.emplace(1);
    while (!q.empty()) {
        int qaq = q.top();
        q.pop();
        if (!vis.test(qaq)) {
            for (auto i: a[qaq]) {
                if (!vis.test(i.first)) {
                    if (dis[qaq] + i.second < dis[i.first]) {
                        dis[i.first] = dis[qaq] + i.second;
                        q.emplace(i.first);
                    }
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    e.resize(n + 1);
    g.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    dijkstra(e);
    for (int i = 1; i <= n; ++i) {
        ans += dis[i];
    }
    dijkstra(g);
    for (int i = 1; i <= n; ++i) {
        ans += dis[i];
    }
    cout << ans;
    return 0;
}

总耗时2.35s，最慢的点825ms。

spfa代码：

#include <bits/stdc++.h>

using namespace std;
int n, m;
long long ans;
vector<vector<pair<int, int>>> e, g;
int dis[1000005];
queue<int> q;

void spfa(vector<vector<pair<int, int>>> a) {
    memset(dis, 0x7f, sizeof(dis));
    dis[1] = 0;
    q.emplace(1);
    while (!q.empty()) {
        int qaq = q.front();
        q.pop();
        for (auto i: a[qaq]) {
            if (dis[qaq] + i.second < dis[i.first]) {
                dis[i.first] = dis[qaq] + i.second;
                q.emplace(i.first);
            }
        }
    }
}


int main() {
    cin >> n >> m;
    e.resize(n + 1);
    g.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    spfa(e);
    for (int i = 1; i <= n; ++i) {
        ans += dis[i];
    }
    spfa(g);
    for (int i = 1; i <= n; ++i) {
        ans += dis[i];
    }
    cout << ans;
    return 0;
}

总耗时2.25s，最慢的点764ms。

所以这题不卡spfa？