#P5109. [CodePlus 2017]大吉大利,晚上吃鸡!

    ID: 4195 传统题 1000ms 512MiB 尝试: 295 已通过: 95 难度: 8 上传者: 标签>难度分类提高+/省选-图论Dijkstra最短路 DAG随机化与近似随机赋权检测动态规划DAG 动态规划排序与序列处理二分查找CF2500

[CodePlus 2017]大吉大利,晚上吃鸡!

[Code+#1] 大吉大利,晚上吃鸡!

题目背景

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

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

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

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

题目描述

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

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

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

  • 大魔王的每一条最短路径都至少经过 A,BA,B 中的一点
  • 不存在同时经过 A,BA,B 的最短路径

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

输入格式

从标准输入读入。第一行四个整数 $n,m,S,T(1 \le n \le 5 \times 10^{4}, 1 \le m \le 5 \times 10^{4}, 1 \le S,T \le n)$ ,含义见题目描述。

接下来输入 mm 行,每行输入三个整数 u,v,w(1≤u,v≤n,1≤w≤109)u,v,w(1 \le u,v \le n, 1 \le w \le 10^{9}) 表示存在一条长度为 ww 的边链接 uu 和 vv 。

输出格式

向标准输出写出一个整数,表示答案。

样例 #1

样例输入 #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

样例 #2

样例输入 #2

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

样例输出 #2

3

样例 #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

提示

样例1解释

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

数据范围

测试点 点数范围 边数范围 特殊性质
1—2 1≤n≤2001\le n\le200 1≤m≤2001\le m\le200 输入是一条链,m=n−1m=n-1,每条输入边满足 v=u+1v=u+1
3—6 无
7—12 1≤n≤20001\le n\le2000 1≤m≤20001\le m\le2000
13—20 1≤n≤5×1041\le n\le5\times10^4 1≤m≤5×1041\le m\le5\times10^4

所有测试点均有 1≤w≤1091\le w\le10^9。