CodeForces 954D-Fight Against Traffic（加邊最短路）

題目連結：https://codeforces.com/problemset/problem/954/D

部落格園食用連結：https://www.cnblogs.com/lonely-wind-/p/13451829.html

Little town Nsk consists of n junctions connected by m bidirectional roads. Each road connects two distinct junctions and no two roads connect the same pair of junctions. It is possible to get from any junction to any other junction by these roads. The distance between two junctions is equal to the minimum possible number of roads on a path between them.

In order to improve the transportation system, the city council asks mayor to build one new road. The problem is that the mayor has just bought a wonderful new car and he really enjoys a ride from his home, located near junction s to work located near junction t. Thus, he wants to build a new road in such a way that the distance between these two junctions won’t decrease.

You are assigned a task to compute the number of pairs of junctions that are not connected by the road, such that if the new road between these two junctions is built the distance between s and t won’t decrease.

Input

The firt line of the input contains integers n , m , s n, m, s n,m,s and t ( 2   ≤   n   ≤   1000 , 1   ≤   m   ≤   1000 , 1   ≤   s ,   t   ≤   n , s   ≠   t ) t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) t(2 ≤ n ≤ 1000,1 ≤ m ≤ 1000,1 ≤ s, t ≤ n,s ​= t) — the number of junctions and the number of roads in Nsk, as well as the indices of junctions where mayors home and work are located respectively. The i-th of the following m lines contains two integers u i u_ i ui​ and v i ( 1   ≤   u i ,   v i   ≤   n , u i   ≠   v i ) v_i (1 ≤ u_ i, v_ i ≤ n, u_i ≠ v i) vi​(1 ≤ ui​, vi​ ≤ n,ui​ ​= vi), meaning that this road connects junctions u i u _i ui​ and v i v_i vi​ directly. It is guaranteed that there is a path between any two junctions and no two roads connect the same pair of junctions.

Output

Print one integer — the number of pairs of junctions not connected by a direct road, such that building a road between these two junctions won’t decrease the distance between junctions s and t.

Examples

Input

5 4 1 5

1 2

2 3

3 4

4 5

Output

Input

5 4 3 5

1 2

2 3

3 4

4 5

Output

5

Input

5 6 1 5

1 2

1 3

1 4

4 5

3 5

2 5

Output

3

emmm，題目讀的有點迷，不過隻要注意到新加一個邊和使得 s s s到 t t t的距離不減少（！！神奇的的要求），并且要求新加邊的兩個點直接之前不能有直達的邊，這題就差不多讀懂了

題目大意：給你一個圖，n個點，m條邊，起點和終點 s , t s,t s,t，然後你需要新加一條邊在兩個點之間，現在問你有多少種加法使得 d i s t ( s , t ) dist(s,t) dist(s,t)不減少。

看題目資料範圍，比較小，那麼我們可以直接枚舉在那兩個點之間建邊，如果對于點 i , j i,j i,j建邊了，若導緻了最短路縮減，也就是 d i s ( s , i ) + d i s ( j , t ) < d i s ( s , t ) dis(s,i)+dis(j,t)<dis(s,t) dis(s,i)+dis(j,t)<dis(s,t) 或着 d i s ( s , j ) + d i s ( i , t ) < d i s ( s , t ) dis(s,j)+dis(i,t)<dis(s,t) dis(s,j)+dis(i,t)<dis(s,t)因為沒法判斷 i , j i,j i,j哪個點離哪個端點最近，是以要判斷兩次。

如果不減少的話也就是大于等于了，那麼我們跑兩次最短路就好了，一個對起點跑，一個對終點跑。然後枚舉判斷一下就好了。對于這種小資料，鄰接矩陣他不香嗎QAQ。

以下是AC代碼：

#include <bits/stdc++.h>
using namespace std;

const int mac=1e3+10;
const int inf=1e9+10;

int mp[mac][mac],diss[mac],n,dist[mac];
int vis[mac];

void dij(int s,int *dis)
{
	memset(vis,0,sizeof vis);
	for (int i=1; i<=n; i++) dis[i]=mp[s][i];
	dis[s]=0; vis[s]=1;
	for (int i=1; i<=n; i++){
		int minn=inf,k=0;
		for (int j=1; j<=n; j++)
			if (!vis[j] && dis[j]<minn)
				minn=dis[j],k=j;
		if (!k) break;
		vis[k]=1;
		for (int j=1; j<=n; j++)
			if (dis[k]+mp[k][j]<dis[j])
				dis[j]=dis[k]+mp[k][j];
	}
}

int main(int argc, char const *argv[])
{
	int m,s,t;
	scanf ("%d%d%d%d",&n,&m,&s,&t);
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++) mp[i][j]=inf;
	for (int i=1; i<=m; i++){
		int u,v;
		scanf ("%d%d",&u,&v);
		mp[u][v]=mp[v][u]=1;
	}
	for (int i=1; i<=n; i++) mp[i][i]=0;
	dij(s,diss); dij(t,dist);
	int ans=0;
	for (int i=1; i<=n; i++){
		for (int j=i+1; j<=n; j++){
			if (mp[i][j]!=inf) continue;
			if (diss[i]+dist[j]+1>=diss[t] && dist[i]+diss[j]+1>=diss[t]) 
				ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}