National Olympiad in Informatics, China, 1998

Day 2, Problem 2 - SERNET Simulation

Computer networking is the highlight of modern technological breakthroughs, and transmission properties is one of the key performance indicators of networks. The SERKOI network development group has recently developed a smaller network called SERNET, and wishes to develop a simulation software to simulate the flow of data within their network.

The SERNET network is composed of servers and cables that connect the servers. Servers use server addresses to be identified, and cables are bidirectional in their ability to transfer data. During the transmission process, data is split into several packets of equal size. Thus, packets are used as the units of transmission. Packets require a certain time to be transmitted on cables, where the transmission time of packets differ on different cables. The time it takes for servers to process the packets is very small compared to the transmission times, and is considered negligible. Other than the data itself, each packet contains the following information:

  • the ID of the packet
  • the ID of the source server
  • the ID of the destination server

The function of networks is to be able to send packets one by one from their source servers to their destination servers. The general procedures for network transmission is as follows. For sending data, the source server takes the packets and makes several copies of it before sending them off to all of the servers it is connected to by cables. Whenever a server receives a packet, if any of the following conditions apply to the packet:

  • the address of the source server is the same as the address of the current server,
  • the address of the destination server is the same as the address of the current server, or
  • the current server has already transmitted packets with the same ID as the received packet

then the packet is kept. Otherwise, the server makes several copies of the packet and sends them off to all the servers that it is connected to. Here, "connected" refers to a direct connection between two servers due to a transmission cable between them.

Your task is to write a program that simulates the transmission of packets on the network.

Input Format

The first line of input consists of one positive integer N (N < 100), the number of servers on SERNET.
The second line contains N distinct positive integers, each no greater than 100, representing the addresses of all of the servers.
The third line contains one positive integer M, the number of cables on SERNET.
The next M lines each contain three integers, the addresses of the two servers at each end of a cable and the transmission time on that cable (a positive integer no greater than 100).
The next line contains one positive integer K (K < 10000), indicating the number of packets in SERNET.
The remaining K lines each give information about a packet, in the format (without commas):

packet ID, time sent out from the source server, source server address, destination server address

The packet IDs in the input will be all be unique, positive integers less than 100000.
The last line of input contains a positive integer T (T < 10000), the output time.
All integers on the same line in the input will be separated by one or more spaces.

Output Format

The output should contain one line with one integer P, the number of packets still being transmitted in the network after a time of T has elapsed (packets with the same ID are counted as the same packet).


All time values in this problem are given in the same unit.
Any cable may simultaneously transmit as many packets as necessary.

Sample Input

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

Sample Output


All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: May 01, 2014

Languages Allowed:

Comments (Search)

You should output the number of different original packets which have at least one copy still being transmitted in the network, not the number of copies remaining.