#6252. 「CodePlus 2017 11 月赛」大吉大利,晚上吃鸡!

内存限制:1024 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

最近《绝地求生:大逃杀》风靡全球,皮皮和毛毛也迷上了这款游戏,他们经常组队玩这款游戏。

在游戏中,皮皮和毛毛最喜欢做的事情就是堵桥,每每有一个好时机都能收到不少的快递。

当然,有些时候并不能堵桥,皮皮和毛毛会选择在其他的必经之路上蹲点。

K 博士作为一个老年人,外加有心脏病,自然是不能玩这款游戏的,但是这并不能妨碍他对这款游戏进行一些理论分析,比如最近他就对皮皮和毛毛的战士很感兴趣。


游戏的地图可以抽象为一张 nn 个点 mm 条无向边的图,节点编号为 11nn ,每条边具有一个正整数的长度。

假定大魔王都会从 SS 点出发到达 TT 点(SSTT 已知),并且只会走最短路,皮皮和毛毛会在 AA 点和 BB 点埋伏大魔王。

为了保证一定能埋伏到大魔王,同时又想留大魔王一条生路,皮皮和毛毛约定 AA 点和 BB 点必须满足:

  1. 大魔王所有可能路径中,必定会经过 AA 点和 BB 点中的任意一点
  2. 大魔王所有可能路径中,不存在一条路径同时经过 AA 点和 BB

K博士想知道,满足上面两个条件的 A,BA,B 点对有多少个,交换 A,BA,B 的顺序算相同的方案。

输入格式

第一行输入四个整数 n,m,S,Tn,m,S,T1n5×104,1m5×104,1S,Tn1 \le n \le 5 \times 10^4, 1 \le m \le 5 \times 10^4, 1 \le S,T \le n),含义见题目描述。

接下来输入 mm 行,每行输入三个整数 u,v,wu,v,w1u,vn,1w1091 \le u,v \le n, 1 \le w \le 10^9)表示存在一条长度为 ww 的边链接 uuvv

输出格式

输出一行表示答案。

样例

样例输入 1

7 7 1 7
1 2 2
2 4 2
4 6 2
6 7 2
1 3 2
3 5 4
5 7 2

样例输出 1

6

样例解释 1

合法的方案为 <2,3>,<2,4>,<4,3>,<4,5>,<6,3>,<6,5><2,3>,<2,4>,<4,3>,<4,5>,<6,3>,<6,5>

样例输入 2

5 5 1 4
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1

样例输出 2

3

样例输入 3

6 7 1 4
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
1 6 2
6 4 2

样例输出 3

5

数据范围与提示

1n5×104,1m5×104,1w1091 \le n \le 5 \times 10^4, 1 \le m \le 5 \times 10^4, 1 \le w \le 10^9


来自 CodePlus 2017 11 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/陈宇 命题/陈宇 验题/邢健开
Git Repo:https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。