National Olympiad in Informatics, China, 1998
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 differs 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 procedure for network transmission is as follows. For sending data, the source server takes the packets and makes several copies of them 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 Specification
The first line of input consists of one positive integer
, the number of servers on SERNET.
The second line contains distinct positive integers, each no greater
than , representing the addresses of all of the servers.
The third line contains one positive integer , the number of cables
on SERNET.
The next 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 ).
The next line contains one positive integer ,
indicating the number of packets in SERNET.
The remaining 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 all be unique, positive integers
less than .
The last line of input contains a positive integer ,
the output time.
All integers on the same line in the input will be separated by one or
more spaces.
Output Specification
The output should contain one line with one integer , the number of packets still being transmitted in the network after a time of has elapsed (packets with the same ID are counted as the same packet).
Guarantees
All time values in this problem are given in the same unit.
Any cable may simultaneously transmit as many packets as necessary.
Sample Input
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
Sample Output
1
Problem translated to English by .
Comments