Problem:


イクタ君は、無向グラフについて異常なほどの思い入れを持っている。イクタ君は、無向グラフ G とその 2 点 s,tの組(G,s,t)のうち、その「うつくしさ」が大きいものが好きである。
組(G,s,t)の「うつくしさ」とは、辺 e = \{u, v\} (u と v は G の異なる 2 点) で、Gにおけるsからtへの最短路の長さが、Gにeをつけくわえた無向グラフにおけるsからtへの最短路の長さより 1 だけ大きいものの個数である。

あなたの仕事は、組(G,s,t)が与えられたとき、その「うつくしさ」を求めるプログラムを書くことである。

Input

入力は以下の形式で与えられる。

N M s t
x1 y1
...
xi yi
...
xM yM

最初に無向グラフの頂点数、辺数、2つの頂点を表す整数N,M,s,tが入力される。
2行目からM+1行目までは辺によって結ばれている2つの頂点が入力される。
(ただし、G の頂点集合を\{1,..., N\}とする。)

Constraints

入力中の各変数は以下の制約を満たす。

 2≤ N ≤ 100,000

 1≤ M ≤ 300,000

 1≤ s,t,xi,yi ≤ N

 s と t とは異なる

 s から t に辿り着けることは保証されている

Output

与えられたグラフをGとしたとき、組(G,s,t)の「うつくしさ」を1行で出力せよ。

Sample Input 1

3 2 1 3
1 2
2 3

Output for the Sample Input 1

1

 頂点1から頂点3に辺を張ると、2点間の最短距離が 1 短くなる。

Sample Input 2

9 8 7 8
2 6
4 9
8 6
9 2
3 8
1 8
8 5
7 9

Output for the Sample Input 2

7

Sample Input 3

4 3 1 4
1 2
3 4
4 1

Output for the Sample Input 3

0

 頂点1と頂点4には既に辺が張られているので、これ以上距離を縮めることはできない。

Sample Input 4

9 7 8 9
9 6
6 5
3 6
3 7
2 5
8 5
1 4

Output for the Sample Input 4

2



Sample input:
3 2 1 3
1 2
2 3


Sample output:
1

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m,s,t = LI()
    xy = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    for x,y in xy:
        e[x].append((y,1))
        e[y].append((x,1))

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    d1 = search(s)
    d2 = search(t)
    tt = d1[t]
    if tt == 1:
        return 0
    if tt == 2:
        return 1
    v1 = collections.defaultdict(int)
    v2 = collections.defaultdict(int)
    for k,v in d1.items():
        v1[v] += 1
    for k,v in d2.items():
        v2[v] += 1
    r = 0
    for i in range(tt-1):
        r += v1[i] * v2[tt-i-2]

    return r



print(main())

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
edges = [[] for _ in range(n)]
for _ in range(m):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  edges[x].append(y)
  edges[y].append(x)

def dist_from(s):
  INF = 10 ** 20
  dist = [INF] * n
  dist[s] = 0
  que = deque()
  que.append((0, s))
  while que:
    score, node = que.popleft()
    for to in edges[node]:
      if dist[to] > score + 1:
        dist[to] = score + 1
        que.append((score + 1, to))
  return dist

dist_from_s = dist_from(s)
dic1 = {}
for i, d in enumerate(dist_from_s):
  if d in dic1:
    dic1[d].add(i)
  else:
    dic1[d] = {i}

dist_from_t = dist_from(t)
dic2 = {}
for i, d in enumerate(dist_from_t):
  if d in dic2:
    dic2[d].add(i)
  else:
    dic2[d] = {i}

st_dist = dist_from_s[t]
ans = 0
for key in dic1:
  another_key = st_dist - key - 2
  if another_key in dic2:
    add = len(dic1[key]) * len(dic2[another_key])
    for u in dic1[key]:
      for to in edges[u]:
        if to in dic2[another_key]:
          add -= 1
    ans += add
print(ans)

Submission status: Accepted

Solution code:
# AOJ 2608: Minus One
# Python3 2018.6.30 bal4u

import heapq
MAX = 0x7fffffff

def dijkstra(dist, start):
	Q = []
	dist[start] = 0
	heapq.heappush(Q, (0, start))
	while Q:
		t, s = heapq.heappop(Q)
		if dist[s] < t: continue
		for e in to[s]:
			nt = t + 1
			if dist[e] > nt:
				dist[e] = nt
				heapq.heappush(Q, (nt, e))

N, M, s, t = map(int, input().split())
s, t = s-1, t-1
to = [[] for i in range(N)]
for i in range(M):
	x, y = map(int, input().split())
	x, y = x-1, y-1
	to[x].append(y)
	to[y].append(x)
smin = [MAX]*N
dijkstra(smin, s)
tmin = [MAX]*N
dijkstra(tmin, t)
scnt = [0]*N
tcnt = [0]*N
for i in range(N):
	if smin[i] < N: scnt[smin[i]] += 1
	if tmin[i] < N: tcnt[tmin[i]] += 1
ans = 0
s = smin[t]-1
for i in range(s): ans += scnt[i]*tcnt[s-1-i]
print(ans)

Submission status: Accepted

Solution code:
N, M, s, t = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().split())
    E[x].append(y)
    E[y].append(x)

closed = [False] * (N+1)
closed[s] = True
dist = [float("inf")] * (N+1)
q = [s]
for dist_ in range(N):
    q_new = []
    for v in q:
        dist[v] = dist_
        for u in E[v]:
            if closed[u]:
                continue
            closed[u] = True
            q_new.append(u)

    q = q_new
    if len(q) == 0:
        break

dist_st = dist[t]

closed = [False] * (N+1)
closed[t] = True
dist_t = [float("inf")] * (N+1)
q = [t]
for dist_ in range(N):
    q_new = []
    for v in q:
        dist_t[v] = dist_
        for u in E[v]:
            if closed[u]:
                continue
            closed[u] = True
            q_new.append(u)

    q = q_new
    if len(q) == 0:
        break
ds = [0] * (dist_st-1)
dt = [0] * (dist_st-1)
for d in dist:
    if d < (dist_st-1):
        ds[d] += 1
for d in dist_t:
    if d < (dist_st-1):
        dt[d] += 1

ans = 0
for a, b in zip(ds, dt[::-1]):
    ans += a*b
print(ans)

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

n,w,s,t = map(int,input().split())

edge = [[] for i in range(n)]
for i in range(w):
    x,y = map(int,input().split())
    edge[x-1].append((1,y-1))
    edge[y-1].append((1,x-1))
a,b = [0]*n,[0]*n
x = dijkstra_heap(s-1)
y = dijkstra_heap(t-1)
distance = x[t-1] - 1
for t in x:
    if t < n:
        a[t] += 1
for t in y:
    if t < n:
        b[t] += 1
ans = 0
for i in range(distance + 1):
    if distance - i > 0:
        ans += a[i] * b[distance - i - 1]
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    while 1:
        n = I()
        if n == 0:
            quit()
        a = LI()
        m = sum(a)/n
        c = 0
        for i in range(n):
            if a[i] <= m:
                c += 1
        print(c)
    return

#B
def B():
    while 1:
        n = I()
        if n == 0:
            quit()
        t = [0 for i in range(24*3600)]
        for i in range(n):
            x,y = input().split()
            x = list(map(int, x.split(":")))
            y = list(map(int, y.split(":")))
            l = x[0]*3600+x[1]*60+x[2]
            r = y[0]*3600+y[1]*60+y[2]
            t[l] += 1
            t[r] -= 1
        ans = 0
        for i in range(24*3600-1):
            t[i+1] += t[i]
            ans = max(ans, t[i])
        print(ans)
    return
#C
def C():
    n = I()
    if n == 0:
        print(1)
    elif n == 1:
        print(2)
    elif n == 2:
        print(1)
    else:
        print(0)
    return

#D
def D():
    def dijkstra(s):
        d = [float("inf") for i in range(n)]
        q = [[0,s]]
        d[s] = 0
        while q:
            dx,x = heappop(q)
            for y in v[x]:
                if dx+1 < d[y]:
                    d[y] = d[x]+1
                    heappush(q,[d[y],y])
        return d
    n,m,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    for i in range(m):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    l = dijkstra(s)
    l2 = dijkstra(t)
    k = l[t]-2
    d = defaultdict(int)
    ans = 0
    for i in l2:
        d[i] += 1
    for i in l:
        ans += d[max(-1,k-i)]
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
# coding: utf-8
import queue
n,m,s,t=map(int,input().split())
table=[[] for i in range(n)]
inf=300001
dist_s=[inf for i in range(n)]
dist_t=[inf for i in range(n)]
s_list=[0 for i in range(inf+1)]
t_list=[0 for i in range(inf+1)]
s-=1;t-=1
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    table[a].append(b)
    table[b].append(a)
dist_s[s]=0
q=queue.Queue()
q.put(s)
while not q.empty():
    p=q.get()
    for e in table[p]:
        if dist_s[e]>dist_s[p]+1:
            dist_s[e]=dist_s[p]+1
            q.put(e)
dist_t[t]=0
q=queue.Queue()
q.put(t)
while not q.empty():
    p=q.get()
    for e in table[p]:
        if dist_t[e]>dist_t[p]+1:
            dist_t[e]=dist_t[p]+1
            q.put(e)
for i in range(n):
    s_list[dist_s[i]]+=1
    t_list[dist_t[i]]+=1
mindist=dist_s[t]
ans=0
for i in range(mindist-1):
    ans+=s_list[i]*t_list[(mindist-2)-i]
print(ans)