| 问题描述 |
|---|
给出一张$$n$$个点，$$m$$条边的带权无向连通图，并记$$D_{i,j}$$为从点$$i$$出发到点$$j$$的最短路径。 已知所有点按照$$1-n$$进行编号，问有多少个点$$u$$满足$$D_{u,1}>D_{u,n}$$。 |
| 输入描述 |
第一行是两个正整数$$n$$和$$m$$分别表示点的数量和边的数量。 接下来$$m$$行，每行三个正整数$$u,v,w$$表示点$$u$$和点$$v$$之间有一条权为$$w$$的无向边。 测试点1：$$1 \leq n \leq 10^5$$，且给出的图是一条链。 测试点2：$$1 \leq n \leq 10^5$$，且给出的图是一棵树。 测试点3：$$1 \leq n \leq 100, 1 \leq m \leq 200$$。 测试点4：$$1 \leq n \leq 10^5, 1 \leq m \leq 2×10^5$$。 对于所有测试点，$$1 \leq w \leq 10^5$$。 |
| 输出描述 |
在一行中输出满足$$D_{u,1}>D_{u,n}$$的点$$u$$的数量。 |
| 样例输入复制样例 |
4 4 1 2 1 2 3 1 3 4 1 4 1 5 |
| 样例输出 |
2 |
| 提示说明 |
在样例中，点$$3$$和$$4$$满足题目要求。 |
| 相关 |