2021牛客暑期多校训练营7 xay loves Floyd

题目大意

有人把写成下面这样，请问这张有向图还有多少个是正确的？

点数，边数，边权

for i from 1 to n
  for j from 1 to n
    for k from 1 to n
      dis[i][j] <- min(dis[i][j], dis[i][k] + dis[k][j])

Solution

考点：实现过程

我们可以在的时间内调用次算法求解到正确。

然后我们就要知道什么样的更新会让按照错误的做法也是正确的。

1. 当存在一条边，有的时候。
2. 当存在三点，有正确，正确，并且这个点在的最短路路径上。

我们用数组表示是正确的，我们用数组表示是正确的。

我们用存下从所有最短路上的点构成的集合。

只要我们枚举每个，再去枚举，让都为真，并且，但是很显然这里看得出来复杂度是的，我们需要考虑用加速。

那么具体实现的时候，我们求出正确的之后，先遍历每一条边，把情况判断掉并且更新数组。

接下来我们跟着他给的错误做法，外层枚举，然后把数组按照升序排序后，按照最近的节点开始往后面更新，如果那么说明里面的全部的点要加入到中，这里发现我们不需要二维的每次用完清空即可，然后加入集合的操作也可以用运算。

至此最后枚举一下，如果任何一位为说明存在一个点让是正确的，我们更新一下数组。

最终把中全部的加起来，还有是无穷大的点一起求合就是答案了。

const int N = 2e3 + 7;
ll n, m;
vector<pai> G[N];
bitset<N> f1[N], f2[N], g[N];
int dis[N][N];

priority_queue<pai, vector<pai>, greater<pai>> pq;
bool vis[N];

void dijkstra(int s, int* d) {
    fill(d + 1, d + 1 + n, INF);
    fill(vis + 1, vis + 1 + n, 0);
    d[s] = 0;
    pq.push({ 0,s });
    while (pq.size()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])    continue;
        vis[u] = 1;
        for (auto& [v, w] : G[u]) {
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({ d[v],v });
            }
        }
    }
}

int tmp[N], ID;
bool cmp(int x, int y) {
    return dis[ID][x] < dis[ID][y];
}

int solve() {
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        G[u].push_back({ v,w });
    }
    for (int i = 1; i <= n; ++i) {
        dijkstra(i, dis[i]);
        f1[i].set(i);
        f2[i].set(i);
    }

    for (int u = 1; u <= n; ++u) {
        for (auto& [v, w] : G[u]) {
            if (dis[u][v] == w) {
                f1[u].set(v);
                f2[v].set(u);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            tmp[j] = j;
            g[j].reset();
            g[j].set(j);
        }

        ID = i;
        sort(tmp + 1, tmp + 1 + n, cmp);
        for (int j = 1; j <= n; ++j) {
            int u = tmp[j];
            for (auto& [v, w] : G[u]) {
                if (dis[i][v] == dis[i][u] + w) {
                    g[v] |= g[u];
                }
            }
        }

        for (int j = 1; j <= n; ++j) {
            if ((f1[i] & f2[j] & g[j]).any()) {
                f1[i].set(j);
                f2[j].set(i);
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; ++i)    res += f1[i].count();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            res += dis[i][j] == INF;
        }
    }

    print(res);

    return 1;
}