Back to Category
d253: [12.09] D - Transmission Mission

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 6 Times | Submit :26 Times | Clicks : 574
Accepted : 2 Users | Submit : 4 Users | Accepted rate : 50%
Time Limit :8000 ms | Memory Limit : 64000 KBytes
Update : 2012-11-01 22:22


Practical Transmission Corporation (PTC) is a mysterious organization with agents on missions all over the world. Because security breaches have become increasingly common, the transmission of data is no longer guaranteed to be safe. Therefore, messages exchanged between agents have edged from relying on telecommunication networks to demanding face-to-face contact with other agents. However, it can be difficult to arrange for all agents to meet together, so a message is often passed on from one to another. The time required for agent A to deliver a message to agent B depends on (1) the capability of A for accurately locating B and (2) the time for effectively conveying the message. There is always a way for any two agents to communicate either directly or indirectly.
The organization can be broken down to 4 departments: the Intelligence (I) Department, the Research (R) Department, the Project Planning (P) Department, and the Execution (E) Department. Communication between different departments can be tricky and consequently requires additional time when compared to communication within same departments. Required time for contact between and within departments are listed in the table below: 
 As part of an organization with a rigid hierarchy, PTCs agents are evaluated on the basis of their loyalty, capability, and achievement to qualify for one of three levels: Superior (S), Intermediate (I), and Apprentice (P). Intermediate and Superior agents are considerably reliable and complete missions within the shortest time, at 3 and 1 hour(s) respectively. Apprentice agents need 5 hours to complete a mission calls for the collaboration of all agents. Missions may also be sorted by urgency into 3 categories: S missions must be completed in 24 hours, A missions in 3 days, B missions in a week. 
Figure 1 shows an example of a relation graph between agents. Each agent has a unique number, 1IS denotes the agent 1 is a Superior in Intelligence (I) Department. The weight on the arrow from 1IS to 2RI means agent 1 needs to take an hour to find agent 2. 
If agent 1 issues a S mission which has to be completed by agent 3, then the command will have to pass agent 2 to give to agent 3 which takes 17 hours including communication time. Since agent 3 is at Intermediate level, he needs 3 hours to complete the mission. Since 20 hours is within a day, agent 3 can report back to agent 1 that the mission will be completed in time. Since it takes 8 hours for the message to reach agent 1, agent 1 will be able to know that the mission will be successful 25 hours after the mission is ordered. Your task is to help the agent who issue a mission knowing that the mission will be success or fail in the shortest time.  

Technical Specifications

  1. The number of test cases would be smaller than or equal to 10.
  2. The number of agents M will satisfy 1 ≤ M ≤ 600. 
  3. The number of missions Q will satisfy 1 ≤ Q ≤ 10.
  4. The time that each agent takes to find an agent he can contact to, is an integer no more than 100 (hours). 


The first line of the input file contains an integer indicating the number of test cases to follow. The first line of each test case contains two integers M and Q, separated by spaces indicating the number of agents and the number of missions respectively. Then it is followed by M + Q lines. Line i (1 ≤ i ≤ M) contains agent i’s information which starts with agent number i, his department D ∈ {I,R, P,E}, his level L ∈ {S, I, P}, followed by the agent number he can reach and the time that will take. Each letter or number are separated by a space. For example, the first test case in ”Sample Input” is the input of the example shown in Figure 1. From line M+1 to line M+Q, each line contains a letter and two integers indicate category, the issuer and the executor of the mission.


For each test case, for each mission, output the shortest time (in hours) it takes for the mission issuer to know the result and the result of the mission (output YES if the mission can be success and NO otherwise) separated by a space. Also output ”==========” in a line between each test case.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4 1
1 I S 2 1
2 R I 3 6
3 I I 4 2 1 7
4 P I 1 4
A 1 3
10 6
1 R S 2 8
2 I S 3 15 1 15
3 R I 4 14 2 12
4 E S 5 1 3 15
5 P S 6 2 4 4
6 I I 7 12 5 7
7 R S 8 9 6 9
8 P S 9 12 7 11
9 E I 10 10 8 2
10 R I 9 11
B 5 2
S 4 5
A 2 9
B 10 3
A 8 9
S 1 7

Sample Output :

25 YES
111 YES
25 YES
221 NO
225 YES
34 YES
190 NO

Hint :

click here to download the problem solving hint

Author :

  Solve it!   Status Forum

50125. ferng1021
(10ms, 1270KB, 2364B)

Program running time may be affected by various factors. Check server system environment information here