P1342 请柬

Problem

题目概述

给你一个有向图，求：

• 从 \(1\) 号点走到每个点的最短路之和
• 从每个点走到 \(1\) 号点的最短路之和。

然后将他们相加。

图论中的小技巧

• 在无向图中，哪些点能走到 \(x\) 点，等价于 \(x\) 点能走到哪些点。
• 在有向图中，哪些点能走到 \(x\) 点，等价于反向建边后，\(x\) 点能走到哪些点。

思路

建两次图。正向、反向。

先在原图上跑一遍优先队列 \(BFS\)，然后在反向建边，在跑一遍，然后加起来。

错误原因

没开 \(LongLong!\) 答案有可能爆 \(int\) ，因为每个 \(w\) 最多是 \(10^9\)。

代码

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <iomanip>
#include <functional>
#include <cmath>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<ll, int> PII;
const int N = 1e6 + 10;
struct node {
    int to, next, len;
} a[N], b[N];
int pre[N], k, n, m, x, y, len;
int pre2[N], k2;
ll d1[N], d2[N];
bool f[N];

void add(int x, int y, int len) {
    a[++k] = (node) {y, pre[x], len};
    pre[x] = k;
}

void add_2(int x, int y, int len) {
    b[++k2] = (node) {y, pre2[x], len};
    pre2[x] = k;
}

void bfs(int s, node a[], ll d[], int pre[]) {
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push(make_pair(0, s));
    memset(f, 0, sizeof(f));
    d[s] = 0;
    while (!q.empty()) {
        PII h = q.top();
        int p = h.second;
        q.pop();
        if (f[p]) continue;
        f[p] = true;
        for (int i = pre[p]; i; i = a[i].next) {
            int to = a[i].to;
            if (d[p] + a[i].len < d[to]) {
                d[to] = a[i].len + d[p];
                q.push(make_pair(d[to], to));
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &len);
        add(x, y, len);
        add_2(y, x, len);
    }
    memset(d1, 0x3f, sizeof(d1));
    memset(d2, 0x3f, sizeof(d2));
    bfs(1, a, d1, pre);
    bfs(1, b, d2, pre2);
    ll ans = 0;
    for (int i = 2; i <= n; i++) ans += d1[i] + d2[i];
    printf("%lld", ans);
    return 0;
}