Codeforces 954D(最短路)

Codeforces 954D
题意：$n$个顶点$m$条边的无向图，现要求添加一条边并且不改变$st$的最短路，问有多少种可行的情况

对于两个点之间加一条边，$dis(s,i)+1+dis(j,t)$和$dis(t,i)+1+dis(j,s)$都不能比最短路短，否则这条路径就成为了最短路。所以预处理$s,t$到每个点的最短路，然后$O(n^2)$枚举$dis(s,i)+1+dis(j,t)$和$dis(t,i)+1+dis(j,s)$都大于等于最短路的边(点对)。

知识点：本题运用了最短路更新的三角不等式的性质，本题加边不能破坏原有的三角不等式性质，否则这条路径就是最短路了，充分运用了最短路的性质，与树的直径证明很像。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;

const int MAXN = 1000 + 10, INF = 1000000000;

struct node {
    int dis, u;
    bool operator < (const node &b) const {
        return dis > b.dis;
    }
};

int n, m, s, t, dis[2][MAXN], vis[MAXN], ma[MAXN][MAXN];
vector<int> G[MAXN];
priority_queue<node> q;

inline void ins(int x, int y) {G[x].push_back(y), G[y].push_back(x), ma[x][y] = ma[y][x] = 1;}

void dij(int TP, int sr) {
    for (int i = 0; i <= n; i++) vis[i] = 0, dis[TP][i] = INF;
    dis[TP][sr] = 0, q.push((node){0, sr});
    while (!q.empty()) {
        node p = q.top(); q.pop();
        if (vis[p.u]) continue; 
        vis[p.u] = 1;
        for (int i = 0; i < (int)G[p.u].size(); i++) {
            int v = G[p.u][i];
            if (dis[TP][v] > dis[TP][p.u] + 1) dis[TP][v] = dis[TP][p.u] + 1, q.push((node){dis[TP][v], v});
        }
    }
}

void clean() {
    ms(ma, 0);
}
int solve() {
    clean();
    for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y);

    dij(0, s), dij(1, t);

    int ans = 0;
    for (int i = 1; i <= n; i++) 
    for (int j = i + 1; j <= n; j++) if (!ma[i][j]) {
        int tmp = min(dis[0][i] + dis[1][j] + 1, dis[1][i] + dis[0][j] + 1);
        if (tmp >= dis[0][t]) ans++;
    }

    printf("%d\n", ans);

    return 0; 
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t), solve();
    return 0;
}