[NOI1998]SERNET模拟

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 关闭时间 2013年02月28日 星期四 23:02
输入文件 sernet.in 输出文件 sernet.out

计算机网络是现代科技发展的热点,传输性能是计算机网络的主要性能指标。SERKOI网络开发小组设计了一种称为SERNET的网络,并希望开发一个模拟软件来模拟该网络的数据传输情况,进而计算出网络的传输性能。

SERNET网络由服务器及连接它们的网络传输线路组成,服务器用服务器地址予以标识,网络传输线路为双向传输线路。网络传输过程中将各种 待传输数据分割为若干个大小相同的数据包,以数据包为单位进行传输。数据包在传输线路上传输时需要一定的传输时间,不同的传输线路的传输时间不同。服务器 处理数据的时间较之于传输时间很小,可忽略不计。每一个数据包中除了包括具体的数据信息外,还含有如下标识信息:

  • 数据包编号
  • 数据包源服务器地址
  • 数据包目的服务器地址

网络传输的功能就是将一个个数据包从源服务器传输到目的服务器。对于每一个数据包,具体的网络传输方案为:

源服务器将待发送的数据包一律复制若干份并向与之相连的所有服务器发送该数据包。服务器接收到一个数据包后,如果该数据包符合下面任何一个条件:

  • 数据包的源服务器地址与本服务器地址相同
  • 数据包的目的服务器地址与本服务器地址相同
  • 本服务器已转发过与该数据包编号相同的数据包

则接收该数据包;否则,服务器将其复制若干份并向与它相连的所有服务器转发该数据包。这里,两台服务器“相连”的含义指它们之间有网络传输线路直接相连。

现在需要你编一个程序来模拟SERNET网络中的数据包传输情况。

输入

输入文件的第一行为一个正整数N(N<100),表示SERNET中服务器的数目。第二行有N个互不相等的不超过100的正整数,表 示每个服务器的地址。 第三行有一个正整数M,表示SERNET中传输线路的数目。接下来的M行每行用三个正整数表示一条传输线路连接的两台服务器的地址以及该传输线路的传输时 间。线路传输时间为不超过100的正整数。 接下来的一行为一个正整数K(K<10000),表示SERNET中数据包的数目。以下的K行每行表示一个数据包的信息,格式为: 数据包编号 起始发送时间 源服务器地址 目的服务器地址

其中数据包编号为互不相同的小于100000的正整数。

输入文件的最后一行为一个正整数T(T<10000),T为输出时刻。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出

输出文件的第一行为一个整数P,表示T时刻后还在网络中传输的数据包数目(编号相同的数据包为同一数据包)。

约定

  • 本题中所有时间量的单位均相同;
  • 每一条传输线路上在同一时刻能传输任意多个数据包。

样例输入

4
57 42 10 93
4
57 42 6
42 93 5
42 10 2
10 93 10
2
433 10 57 10
5678 11 42 93
23

样例输出

1