题意：
给出n点m边的无向图，现在要求在没有边的两点之前连边，并且s到t的最短路长度不变，问满足条件的边数。
思路：
从起点和终点分别跑一遍最短路，然后枚举一下未出现的边统计即可。
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } #define PI acos(-1) #define x first #define y second const int maxn=1e6+7,inf=0x3f3f3f3f; int n,m,s,t; struct node{ int e,ne; }edge[maxn]; int h[maxn],idx; void add(int u,int v){ edge[idx]={v,h[u]},h[u]=idx++; } int dis[maxn],st[maxn],dis1[maxn]; void dijkstra(int s){ memset(dis,0x3f,sizeof dis); memset(st,0,sizeof st); dis[s]=0; ///建立一个维护最小值的优先队列 priority_queue<PII,vector<PII>,greater<PII>>heap; heap.push({0,s});///起始点放入队列 while(heap.size()){ auto t=heap.top();///最小值 heap.pop(); int ver=t.second,d=t.first; if(st[ver]) continue;///该点更新 st[ver]=true; for(int i=h[ver];i!=-1;i=edge[i].ne){ int j=edge[i].e; if(dis[j]>d+1){ dis[j]=d+1; heap.push({dis[j],j}); } } } } void dijkstra1(int s){ memset(dis1,0x3f,sizeof dis1); memset(st,0,sizeof st); dis1[s]=0; ///建立一个维护最小值的优先队列 priority_queue<PII,vector<PII>,greater<PII>>heap; heap.push({0,s});///起始点放入队列 while(heap.size()){ auto t=heap.top();///最小值 heap.pop(); int ver=t.second,d=t.first; if(st[ver]) continue;///该点更新 st[ver]=true; for(int i=h[ver];i!=-1;i=edge[i].ne){ int j=edge[i].e; if(dis1[j]>d+1){ dis1[j]=d+1; heap.push({dis1[j],j}); } } } } int g[1100][1100]; int main() { memset(h,-1,sizeof h);idx=0; n=read,m=read,s=read,t=read; rep(i,1,m){ int u=read,v=read; add(u,v);add(v,u); g[u][v]=g[v][u]=1; } dijkstra(s); dijkstra1(t); int res=0; for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(!g[i][j]){ int d1=dis[i]+dis1[j]+1,d2=dis[j]+dis1[i]+1; if(d1>=dis[t]&&d2>=dis[t]) res++; } printf("%d\n",res); return 0; }
