建个图,跑两个bfs算下距离,假如不是因为这条边的产生使得距离变短了,就ans++.n^2枚举添加的边.
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
vector<int>v[N];
map<int,int>mp[N];
int dis1[N],dis2[N],vis1[N],vis2[N];//dis1是所有点到s的最短距离 dis2是所有点到t的最短距离
queue<int>q1,q2;
void bfs1()//处理dis1.
{
    while(q1.size())
    {
        int temp=q1.front();
        q1.pop();
        for(int i=0;i<v[temp].size();i++)
        {
            int pos=v[temp][i];
            if(vis1[pos]) continue;
            vis1[pos]=1;
            dis1[pos]=dis1[temp]+1;
            q1.push(pos);
        }
    }
}

void bfs2()//处理dis2.
{
    while(q2.size())
    {
        int temp=q2.front();
        q2.pop();
        for(int i=0;i<v[temp].size();i++)
        {
            int pos=v[temp][i];
            if(vis2[pos]) continue;
            vis2[pos]=1;
            dis2[pos]=dis2[temp]+1;
            q2.push(pos);
        }
    }
}


int main()
{
    int n,m,s,t,ans=0;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
        mp[x][y]=1;mp[y][x]=1;
    }
    q1.push(s);vis1[s]=1;
    bfs1();
    q2.push(t);vis2[t]=1;
    bfs2();
    //cout<<dis1[t]<<' '<<dis2[2]<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(mp[i][j])    continue;
            if(dis1[i]+dis2[j]+1>=dis2[s]&&dis1[j]+dis2[i]+1>=dis2[s])  ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}