PID354 / 魔法阵
题目描述

在Alyosha的带领下,龙族赢得了战争。但是战争带来的永远是创伤。

Alyosha的伟大之处不在于他过人的军事才能,而是在于他在战争后为这片大陆重新带来了生机。

Alyosha为了实现他的伟大愿望,布置了一个上古时期流传下来的魔法阵。这个魔法阵中有N颗魔法石,方便起见,将他们编号1~N,每块魔法石都有一个法力值,为1~10之间(含1和10)的正整数。某些魔法石之间用一些魔纹连接,连接是双向的,魔纹有一定的长度。魔法石之间可以通过其他魔法石和这些魔法石之间的魔纹连通,一个连通的值即是这些魔纹的长度和。两块魔法石之间的距离就是它们之间所有连通的值中最小的那个。每块魔法石最多和10块魔法石直接用魔纹连接。当Alyosha将自己的魔法力注入阵中后,魔法阵就可以与上古时期的生命之神的法力沟通,给大陆带来生命力。

为了更好地了解魔法阵的结构,我们做出了如下定义:

魔法石i对魔法石j敏感,当且仅当不存在魔法石k(k可能与i相等)到i的距离比j到i的距离短且k的魔法值比j的魔法值高。这时(i,j)叫做一个敏感的魔法石对。

显然,i对j敏感并不表示j对i敏感。也就是说(i,j)与(j,i)是不同的。魔法石i对自己对自己是不敏感的。

现在,给出这个魔法阵的具体情况,请你求出所有敏感的魔法石对的数目。

输入格式

第一行:N(N<2000)和M,表示魔法石数目和魔纹数目。

第2..N+1行:每行一个正整数rank(i),表示魔法石i的法力值。

第N+2~N+M+1 行:每行三个正整数i,j,l(i,j),表示i与j之间有一道长度为l(i,j)的魔纹。

输出格式

一行,表示敏感的魔法石对的数目。数据保证结果的最大值是3*n。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论