题解
1.题目大意
给定一个无向图，所有边权都为1
给定一个起点 \(s\) 和 终点 \(t\)
求满足以下条件数对(u,v)的数量：
- 1.图中不存在(u,v)这条边
- 2.若在图中加入(u,v)这条边，\(s\) 到 \(t\) 的距离不变
2.思路
考虑加入(u,v)后改变了什么
首先如果加入(u,v)后会改变 \(s\) 到 \(t\) 的距离
那么说明新的最短路一定经过(u,v)
所以现在我们只需要计算一个东西：
\(s\) 到 \(t\) 一定要经过(u,v)的路径的长度
如果这个长度小于本来 \(s\) 到 \(t\) 的距离，
那么加入(u,v)后会让距离变小
否则，不变
那么怎么计算这个路径的长度呢？
我们发现这条路径可以拆成三个部分：
- 从 \(s\) 到 \(u\) 的最短路径
- 从 \(u\) 到 \(v\) 的最短路径（长度就是1）
- 从 \(v\) 到 \(t\) 的最短路径
这很好做，直接bfs预处理 \(s\) 到所有点的最短距离和所有点到 \(t\) 的最短距离
于是我们就做完了
总结一下：
- 1.bfs计算 \(s\) 到所有点的最短距离和所有点到 \(t\) 的最短距离
- 2.枚举(u,v)，计算\(s\) 到 \(t\) 一定要经过(u,v)的路径的长度 \(l\) ，统计满足 \(l<s到t的距离\) 的(u,v)个数
3.Code
#include<bits/stdc++.h>using namespace std;
int s,t,n,m,dis1[200010],dis2[200010],ji[1010][1010];
vector<int>e[200010];
main(){cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;e[u].push_back(v);e[v].push_back(u);ji[u][v]=ji[v][u]=1;}queue<int>q;q.push(s);memset(dis1,0x3f,sizeof dis1);dis1[s]=0;while(q.size()){int u=q.front();q.pop();for(auto v:e[u]){if(dis1[v]>dis1[u]+1){dis1[v]=dis1[u]+1;q.push(v);}}}q.push(t);memset(dis2,0x3f,sizeof dis2);dis2[t]=0;while(q.size()){int u=q.front();q.pop();for(auto v:e[u]){if(dis2[v]>dis2[u]+1){dis2[v]=dis2[u]+1;q.push(v);}}}int ans=0;//cout<<dis1[t]<<endl;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(dis1[i]+dis2[j]+1>=dis1[t] and dis2[i]+dis1[j]+1>=dis1[t] and !ji[i][j])ans++;}}cout<<ans;return 0;
}