← 返回题目列表

AtCoder · icpc2013summer_day3_b

B. 减一

中文机器翻译题面 查看原题

Ikta 对无向图有异常多的依恋。 Ikta-kun 是一个无向图 G 和这两点 s,t对(G,s,t)中,我最喜欢最美的。 组(G,s,t)的“美”就是缘 e = \{u, v\} (u 和 v 是 它仅由 G 在两个不同的点), 在G中 到s我决定将所有值添加到t的最短路径的长度是G至 在带有e的无向图中 它是比到s我决定将所有值添加到t的最短路径长度大 1 的对象数量。

你的工作是 给定(G,s,t),任务是编写一个寻求其“美感”的程序。

输入

输入按以下格式给出。

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

首先是无向图中的顶点数、边数以及代表两个顶点的整数。 输入N,M,s,t。 从第二行开始 直到M+1行,输入由边连接的两个顶点。 (但是,G 的顶点集\{1,..., N\}。 )

约束

输入中的每个变量都满足以下约束。 与

  • 2\leq N \leq 100,000

  • 1\leq M \leq 300,000

  • 1\leq s,t,xi,yi \leq N

  • s 和 t 不同 保证您可以达到

  • s 我决定将所有值添加到 t 保证你能达到

输出

给定的图表 当G时,设置 一行输出(G,s,t)的“美”。

示例输入 1

3 2 1 3
1 2
2 3

样本输入 1 的输出

1
  • 如果将一条边从顶点 1 延伸到顶点 3,则两点之间的最短距离将缩短 1。

示例输入 2

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

样本输入 2 的输出

7

示例输入 3

4 3 1 4
1 2
3 4
4 1

样本输入 3 的输出

0
  • 由于顶点 1 和 4 之间已经存在一条边,因此无法进一步缩短距离。

示例输入 4

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

样本输入 4 的输出

2