P1261 Server Storage Information Problem

The Kingdom of Byteland is preparing to build a large network among its servers and provide various services. The network consists of $n$ servers, connected by bidirectional links. There is at most one direct link between any pair of servers. Each server is directly connected to at most $10$ servers. Furthermore, there is a path between any two servers. Each transmission link has a fixed length. Let $\delta(v,w)$ denote the length of the shortest path between servers $v$ and $w$, and for any $v$ we have $\delta(v,v)=0$. Some servers provide more services than others and are therefore more important. We use $r(v)$ to denote the importance $\texttt{rank}$ of server $v$. A higher $\texttt{rank}$ means a more important server. Each server stores information about nearby servers. Of course, not all servers’ information is stored—only the interesting ones. Server $v$ is interested in server $w$ if there does not exist a server $u$ such that $r(u)>r(w)$ and $\delta(v,u)\le\delta(v,w)$. For example, all servers with the highest $\texttt{rank}$ are interesting to every other server. If $v$ has the highest $\texttt{rank}$, then since $\delta(v,v)=0$, $v$ is interested only in servers with the highest $\texttt{rank}$. We define $B(v)$ as the set of servers that server $v$ is interested in. We want to compute the total amount of information stored by all servers, i.e., the sum of $|B(v)|$ over all servers. Byteland does not want to store a large amount of data, so the total amount of stored data (the sum of $|B(v)|$) will not exceed $30n$. Your task is to write a program that reads the network layout of Byteland and computes the total amount of information stored by all servers.

The first line contains two integers $n$ and $m$. Here $n$ is the number of servers and $m$ is the number of transmission links. The next $n$ lines each contain one integer. The integer on the $i$-th line is $r(i)$, the $\texttt{rank}$ of server $i$. The next $m$ lines each describe a transmission link with three integers $a,b,t$. Here $a$ and $b$ are the indices of the two servers connected by the link, and $t$ is the length of the link.

Output a single integer: the total amount of data stored by all servers, i.e., the sum of $|B(v)|$.

Output explanation: $B(1)=\{1,2\},B(2)=\{2\},B(3)=\{2,3\},B(4)=\{1,2,3,4\}$. Constraints: $1\le n\le30000,1\le m\le5n$ $1\le r(i)\le 10$ $1\le t\le 1000,1\le a,b\le n,a\neq b$. Translated by ChatGPT 5