九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1495-九度Online Judge,用代码记录你的成长之路!

题目1495:关键点

时间限制:1 秒

内存限制:128 兆

特殊判题:

提交:476

解决:99

题目描述:

在一个无权图中,两个节点间的最短距离可以看成从一个节点出发到达另一个节点至少需要经过的边的个数。
同时,任意两个节点间的最短路径可能有多条,使得从一个节点出发可以有多条最短路径可以选择,并且沿着这些路径到达目标节点所经过的边的个数都是一样的。
但是在图中有那么一些特殊的节点,如果去除这些点,那么从某个初始节点到某个终止节点的最短路径长度要么变长,要么这两个节点变得不连通。这些点被称为最短路径上的关键点。
现给定一个无权图,以及起始节点和终止节点,要求输出该图上,这对节点间最短路径上的关键点数目。

输入:

输入包含多组测试数据,每组测试数据第一行为4个整数n(1<=n<=10000),m(1<=m<=100000),s(1<=s<=n),t(1<=t<=n)。分别代表该图中的节点个数n,边数量m,起始节点s,终止节点t。
接下去m行描述边的信息,每行两个整数a,b(1<=a,b<=n 且 a != b)。表示节点a和节点b之间有一条边。

输出:

对于每组测试数据,输出给定的这对节点间最短路径上的关键点数目。注意:若给定两个节点间不连通,则我们认为其关键点数目是0。

样例输入:
5 5 1 5
1 2
1 3
2 4
3 4
4 5
4 4 1 4
1 2
2 4
3 4
1 3
样例输出:
1
0
来源:
2013年王道论坛计算机考研机试全真模拟考试