AOJ 2608 Minus One

これは比較的解きやすいと思う．
最後の最後に気を付けることあるけど．

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2608

解法
頂点sとtからbfsを用いて，sとtからの全ての点への最短距離を求める．
iからjへの最短距離をdist(i,j)とおくと
求めるものはdist(s,i)+1+dist(j,t)=dist(s,t)を満たす(i,j)の組である．
sとtからの最短距離がiである頂点数を前計算すれば，簡単に求められる．

計算量は，bfsの部分でO(N)，組み合わせの計算でO(N)，よってO(N)

ソースコードは以下の通り

const int vmax=100010;
int sdist[vmax];
int tdist[vmax];

ll snum[vmax];
ll tnum[vmax];

vi graph[vmax];

int main(void){
	int n,m,s,t;
	cin  >> n >> m >> s >> t;
	s--,t--;

	rep(i,m){
		int x,y;
		cin >> x >> y;
		x--,y--;
		graph[x].pb(y);
		graph[y].pb(x);
	}
	rep(i,vmax) sdist[i]=tdist[i]=-1;

	queue<pii> q;
	sdist[s]=0; q.push(mp(s,0));
	while(!q.empty()){
		pii cur=q.front();q.pop();
		int v=cur.first;
		int c=cur.second;
		for(auto &v2:graph[v]){
			if(sdist[v2]==-1){
				sdist[v2]=c+1;
				q.push(mp(v2,c+1));
			}
		}
	}

	tdist[t]=0; q.push(mp(t,0));
	while(!q.empty()){
		pii cur=q.front();q.pop();
		int v=cur.first;
		int c=cur.second;
		for(auto &v2:graph[v]){
			if(tdist[v2]==-1){
				tdist[v2]=c+1;
				q.push(mp(v2,c+1));
			}
		}
	}
	rep(i,n) snum[sdist[i]]++;
	rep(i,n) tnum[tdist[i]]++;
	int sp=sdist[t];
	ll ans=0LL;
	rep(i,sp-1) ans+=snum[i]*tnum[sp-2-i];
	cout << ans << endl;
	return 0;
}