为缓解 S 城与日俱增的交通压力,S 城的市长准备修一条路
S 城共有 n 个街区,它们由 m 条双向道路相连,每条道路的长度相等
作为 S 城的天才,小 X 了解到 S 城的交通压力主要来自于最繁华的 S 街区和 T 街区
如果新修的路不能使 S 街区到 T 街区的距离缩短,就不能缓解 S 城的交通压力
S 城的市长自然不了解这一点。现在小 X 想知道,有多少种修路方案不能缓解 S 城的交通压力
注意,对于修路方案 (u,v) 和 (v,u) 视为同一种方案,新修的路不能在原图中存在
又是一道送分题,\(\Theta{(n)}\) 预处理出所有点距离两个繁华街区的距离
\(\Theta{(n^2)}\) 暴力查询每条路径是否会让路径变短
本来想的优化是:如果两个点都不在两繁华街区之间,说明这条路对路径不会有任何影响,直接continue
结果发现查询每条路本来就是 \(\Theta{(1)}\) 的,所以这优化并没有什么用……
代码
#include<bits/stdc++.h>
#define inf 1234567890
using namespace std;
int n,m,s,t,u,v;
struct Edge
{
int next,to;
}edge[4005];
int cnt=0,head[4005];
int diss[2005],dist[2005];
bool viss[2005],vist[2005];
inline void add_edge(int from,int to)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
head[from]=cnt;
}
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
inline void init()
{
for(register int i=1;i<=n;++i) diss[i]=dist[i]=inf;
diss[s]=0;dist[t]=0;
}
queue<int> q;
int exsts[2005],nos[2005];
void bfss(int u)
{
q.push(u);
while(!q.empty())
{
int u=q.front();q.pop();nos[u]=0;
for(register int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(diss[v]>diss[u]+1)
{
diss[v]=diss[u]+1;
if(!nos[v])
{
nos[v]=1;
q.push(v);
}
}
}
}
}
int exstt[2005],nott[2005];
void bfst(int u)
{
q.push(u);
while(!q.empty())
{
int u=q.front();q.pop();nott[u]=0;
for(register int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(dist[v]>dist[u]+1)
{
dist[v]=dist[u]+1;
if(!nott[v])
{
nott[v]=1;
q.push(v);
}
}
}
}
}
bool hav[1005][1005];
bool usef[2005];//有用的点
int main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
read(n);read(m);read(s);read(t);
init();
for(register int i=1;i<=m;++i)
{
read(u);read(v);
add_edge(u,v);
add_edge(v,u);
hav[u][v]=hav[v][u]=1;
}
bfss(s); bfst(t);
int predis=diss[t];
int ans=0;
for(register int i=1;i<=n;++i) if(diss[i]>predis&&dist[i]>predis) usef[i]=1;
// cout<<"!"<<endl;
// cout<<predis<<endl;
// cout<<diss[1]<<" "<<dist[3]<<" "<<dist[1]<<" "<<diss[3]<<endl;
for(register int i=1;i<n;++i)//枚举每一种修路方法
{
for(register int j=i+1;j<=n;++j)
{
if(i==j||hav[i][j]) continue;
if(usef[i]&&usef[j])
{
ans++;
// cout<<"useless: "<<i<<" "<<j<<endl;
continue;
}
else if(diss[i]+1+dist[j]<predis) continue;
else if(dist[i]+1+diss[j]<predis) continue;
// cout<<i<<" "<<j<<endl;
ans++;
}
}
printf("%d\n",ans);
return 0;
}