资讯首页 热点资讯初中高中竞赛自招

文库 > 竞赛自招 > 正文

信息学竞赛测试题:魔法阵

273 0 0 2019-05-20 10:48:03

题目描述

在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。


样例输入


6 5

4

2

3

2

2

4

1 2 1

2 3 1

3 4 1

4 5 1

5 6 1


样例输出


14

我要评论 0条评论

0/300

自律公约

网友评论

来第一个评论吧