主观题：Ambulance Dispatch
Given the map of a city, with all the ambulance dispatch centers (救护车派遣中心) and all the pick-up spots marked. You are supposed to write a program to process the emergency calls. It is assumed that the callers are waiting at some pick-up spot. You must inform the nearest (that is, to take the minimum time to reach the spot) dispatch center if that center has at least one ambulance available. Note: a center without any ambulance must not be considered.
In case your options are not unique, inform the one with the largest number of ambulances available. If there is still a tie, choose the one that can pass the least number of streets to reach the spot, which is guaranteed to be unique.
### Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers $$N_s$$ ($$\le 10^3$$) and $$N_a$$ ($$\le 10$$), which are the total number of pick-up spots and the number of ambulance dispatch centers, respectively. Hence the pick-up spots are numbered from 1 to $$N_s$$, and the ambulance dispatch centers are numbered from $$A-1$$ to $$A-N_a$$.
The next line gives $$N_a$$ non-negative integers, where the $$i$$-th integer is the number of available ambulances at the $$i$$-th center. All the integers are no larger than 100.
In the next line a positive number $$M$$ ($$\le 10^4$$) is given as the number of streets connecting the spots and the centers. Then $$M$$ lines follow, each describes a street by giving the indices of the spots or centers at the two ends, followed by the time taken to pass this street, which is a positive integer no larger than 100.
Finally the number of emergency calls, $$K$$, is given as a positive integer no larger than $$10^3$$, followed by $$K$$ indices of pick-up spots.
All the inputs in a line are separated by a space.
### Output Specification:
For each of the $$K$$ calls, first print in a line the path from the center that must send an ambulance to the calling spot. All the nodes must be separated by exactly one space and there must be no extra space at the beginning or the end of the line. Then print the minimum time taken to reach the spot in the next line. It is assumed that the center will send an ambulance after each call. If no ambulance is available, just print All Busy in a line. It is guaranteed that all the spots are connected to all the centers.
### Sample Input:
in
7 3
3 2 2
16
A-1 2 4
A-1 3 2
3 A-2 1
4 A-3 1
A-1 4 3
6 7 1
1 7 3
1 3 3
3 4 1
6 A-3 5
6 5 2
5 7 1
A-2 7 5
A-2 1 1
3 5 1
5 A-3 2
8
6 7 5 4 6 4 3 2
### Sample Output:
out
A-3 5 6
4
A-2 3 5 7
3
A-3 5
2
A-2 3 4
2
A-1 3 5 6
5
A-1 4
3
A-1 3
2
All Busy
### Grading Policy:
Chapter 1: Introduction (6 pts.)
Chapter 2: Algorithm Specification (12 pts.)
Chapter 3: Testing Results (20 pts.)
Chapter 4: Analysis and Comments (10 pts.)
Write the program (50 pts.) with sufficient comments.
Overall style of documentation (2 pts.)
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
the cover page is not complete (-1)
the introduction is a simple copy + paste of the assignment statement (-3)
the introduction is not very clear -- in this chapter one is supposed to make it clear WHAT is to be done, besides why one is doing it (-1 ~ -2)
others - please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of all the key algorithms involved (+3 pts. for the data structures; +7 pts. for the algorithms), plus a sketch of the main program (+2 pts.). Deduct points if:
the algorithm specification is not complete – the data structure description is missing (-2)
the algorithm specification is not complete –the key algorithm is missing (-3 ~ -7)
not making one's algorithm easier to understand than a simple program (-2)
only a program + comments, which is not acceptable (-4)
others - please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points if:
the document looks messy - some of the data in the charts and tables are missing (-1)
the hand-in is not zipped with proper folders (-1)
the hand-in is not complete - some files are missing (-1)
others - please specify in the final comments.
Item 4: 20 points
A complete table of test cases with testing purposes must be given in Chapter 3. A minimum of 3 test cases must be given (+10 pts.). Besides at least one comprehensive test (+6 pts.), the cases with the smallest or the largest sizes, and some extreme cases must be covered (+4 pts.). Deduct points if:
the testing results contain some test cases, however with no specification on their purposes (-3)
the testing results contain some test cases, but there are still bugs missed (-1 ~ -10)
the testing results contain too few cases and hence is too simple to be considered as being complete (-4 ~ -10)
others - please specify in the final comments.
Item 5: 10 points
Analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms are supposed to be given in Chapter 4. Bonus point for discussing more than just one algorithm (+2 pts.). Deduct points if:
analysis of the complexities of time and/or space is missing -- one must show how one has reached the conclusions, instead of simply listing them (-4)
others - please specify in the final comments.
Item 6: 50 points
For the programming work, deduct points if:
the programs are not working properly (-1 ~ -20)
the programs are not well-commented (-50)
the programming style is too messy to be judged (-1 ~ -5)
others - please specify in the final comments.
In case your options are not unique, inform the one with the largest number of ambulances available. If there is still a tie, choose the one that can pass the least number of streets to reach the spot, which is guaranteed to be unique.
### Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers $$N_s$$ ($$\le 10^3$$) and $$N_a$$ ($$\le 10$$), which are the total number of pick-up spots and the number of ambulance dispatch centers, respectively. Hence the pick-up spots are numbered from 1 to $$N_s$$, and the ambulance dispatch centers are numbered from $$A-1$$ to $$A-N_a$$.
The next line gives $$N_a$$ non-negative integers, where the $$i$$-th integer is the number of available ambulances at the $$i$$-th center. All the integers are no larger than 100.
In the next line a positive number $$M$$ ($$\le 10^4$$) is given as the number of streets connecting the spots and the centers. Then $$M$$ lines follow, each describes a street by giving the indices of the spots or centers at the two ends, followed by the time taken to pass this street, which is a positive integer no larger than 100.
Finally the number of emergency calls, $$K$$, is given as a positive integer no larger than $$10^3$$, followed by $$K$$ indices of pick-up spots.
All the inputs in a line are separated by a space.
### Output Specification:
For each of the $$K$$ calls, first print in a line the path from the center that must send an ambulance to the calling spot. All the nodes must be separated by exactly one space and there must be no extra space at the beginning or the end of the line. Then print the minimum time taken to reach the spot in the next line. It is assumed that the center will send an ambulance after each call. If no ambulance is available, just print All Busy in a line. It is guaranteed that all the spots are connected to all the centers.
### Sample Input:
in
7 3
3 2 2
16
A-1 2 4
A-1 3 2
3 A-2 1
4 A-3 1
A-1 4 3
6 7 1
1 7 3
1 3 3
3 4 1
6 A-3 5
6 5 2
5 7 1
A-2 7 5
A-2 1 1
3 5 1
5 A-3 2
8
6 7 5 4 6 4 3 2
### Sample Output:
out
A-3 5 6
4
A-2 3 5 7
3
A-3 5
2
A-2 3 4
2
A-1 3 5 6
5
A-1 4
3
A-1 3
2
All Busy
### Grading Policy:
Chapter 1: Introduction (6 pts.)
Chapter 2: Algorithm Specification (12 pts.)
Chapter 3: Testing Results (20 pts.)
Chapter 4: Analysis and Comments (10 pts.)
Write the program (50 pts.) with sufficient comments.
Overall style of documentation (2 pts.)
答案：Rubric items: 6
Item 1: 6 points
The cover page must be presented with the title and the date of completion (+2 pts.). A complete problem description must be given in Chapter 1 (+4 pts.). Deduct points if:
the cover page is not complete (-1)
the introduction is a simple copy + paste of the assignment statement (-3)
the introduction is not very clear -- in this chapter one is supposed to make it clear WHAT is to be done, besides why one is doing it (-1 ~ -2)
others - please specify in the final comments.
Item 2: 12 points
Chapter 2 is supposed to contain the descriptions (pseudo-code preferred) of all the key algorithms involved (+3 pts. for the data structures; +7 pts. for the algorithms), plus a sketch of the main program (+2 pts.). Deduct points if:
the algorithm specification is not complete – the data structure description is missing (-2)
the algorithm specification is not complete –the key algorithm is missing (-3 ~ -7)
not making one's algorithm easier to understand than a simple program (-2)
only a program + comments, which is not acceptable (-4)
others - please specify in the final comments.
Item 3: 2 points
The overall style of documentation is supposed to be neat and clear. Deduct (at most 2) points if:
the document looks messy - some of the data in the charts and tables are missing (-1)
the hand-in is not zipped with proper folders (-1)
the hand-in is not complete - some files are missing (-1)
others - please specify in the final comments.
Item 4: 20 points
A complete table of test cases with testing purposes must be given in Chapter 3. A minimum of 3 test cases must be given (+10 pts.). Besides at least one comprehensive test (+6 pts.), the cases with the smallest or the largest sizes, and some extreme cases must be covered (+4 pts.). Deduct points if:
the testing results contain some test cases, however with no specification on their purposes (-3)
the testing results contain some test cases, but there are still bugs missed (-1 ~ -10)
the testing results contain too few cases and hence is too simple to be considered as being complete (-4 ~ -10)
others - please specify in the final comments.
Item 5: 10 points
Analysis of both the time (+5 pts.) and space (+5 pts.) complexities of the algorithms are supposed to be given in Chapter 4. Bonus point for discussing more than just one algorithm (+2 pts.). Deduct points if:
analysis of the complexities of time and/or space is missing -- one must show how one has reached the conclusions, instead of simply listing them (-4)
others - please specify in the final comments.
Item 6: 50 points
For the programming work, deduct points if:
the programs are not working properly (-1 ~ -20)
the programs are not well-commented (-50)
the programming style is too messy to be judged (-1 ~ -5)
others - please specify in the final comments.
