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).
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
All Submissions
Best Solutions
Point Value: 12 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: May 01, 2014
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)