思路:
求出每个数据包在网络中存在的最(晚)后时刻,不妨记作 $last$,则 $last>T$ 的数据包数即是答案。
要点:
1、对于被复制的某数据包,服务器 $i$ 只会转发最早且第一次到达自己的那个复制包,因为后续到达的相同数据包将会被接收而不再转发;
2、最早到达服务器 $i$ 的复制包一定是通过最短路(最少传输时间)抵达的,然后通过服务器 $i$ 的最长出边转发出去的复制包可能会在网络中存在更久;
3、那么,对于服务器 $i$ 而言,某数据包传输过程分为两段:(1)从起点 $s$ 沿最短路抵达服务器 $i$;(2)沿服务器 $i$ 最长边转发至邻接服务器;
则:某数据包传输时间 $=$ $shortest[i]$ $+$ $farest[i]$,前者是从 $s \sim i$ 的最短路,后者是 $i$ 的最长出边;
综上,$last = max\{ shortest[i] + farest[i] \} + startime$(开始传输时刻)