[CodeForces954D]Fight Against Traffic（最短路）

Description

Solution

从起点和终点分别做一次最短路并记录结果

枚举每一条可能的边判断

Code

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

#define N 1010

using namespace std;

struct info{int to,nex;}e[N*2];

int n,m,s,t,tot,head[N],dis[N],ddis[N],Ans;

bool g[N][N];

inline int read(){

    int 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;

}

inline void Link(int u,int v){

    e[++tot].to=v;e[tot].nex=head[u];head[u]=tot;

}

bool vis[N];

void bfs(int d[],int s){

	memset(vis,0,sizeof(vis));

	queue<int> q;

	q.push(s);

	d[s]=0,vis[s]=1;

	while(!q.empty()){

		int u=q.front();q.pop();

		for(int i=head[u];i;i=e[i].nex){

			int v=e[i].to;

			if(vis[v]) continue;

			d[v]=d[u]+1;

			q.push(v);

			vis[v]=1;

		}

	}

}

int main(){

    n=read(),m=read(),s=read(),t=read();

    while(m--){int u=read(),v=read();Link(u,v);Link(v,u);g[u][v]=g[v][u]=1;}

    bfs(dis,s);

    bfs(ddis,t);

    for(int i=1;i<=n;++i)

    	for(int j=i+1;j<=n;++j)

    		if(!g[i][j]&&dis[i]+ddis[j]+1>=dis[t]&&dis[j]+ddis[i]+1>=dis[t])

    			Ans++;

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

    return 0;

}

巴特西

[CodeForces954D]Fight Against Traffic（最短路）

Description

Solution

Code

最新文章

热门文章