主观题：Dijkstra Sequence
Dijkstra's algorithm is one of the very famous greedy algorithms. It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to all the other vertices of the given graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. In this algorithm, a set contains vertices included in shortest path tree is maintained. During each step, we find one vertex which is not yet included and has a minimum distance from the source, and collect it into the set. Hence step by step an ordered sequence of vertices, let's call it **Dijkstra sequence**, is generated by Dijkstra's algorithm. On the other hand, for a given graph, there could be more than one Dijkstra sequence. Your job is to check whether a given sequence is Dijkstra sequence or not. ### Input Specification: Each input file contains one test case. For each case, the first line contains two positive integers $$N_v$$ ($$\le 10^3$$) and $$N_e$$ ($$\le 10^5$$), which are the total numbers of vertices and edges, respectively. Hence the vertices are numbered from 1 to $$N_v$$. Then $$N_e$$ lines follow, each describes an edge by giving the indices of the vertices at the two ends, followed by a positive integer weight ($$\le 100$$) of the edge. It is guaranteed that the given graph is connected. Finally the number of queries, $$K$$, is given as a positive integer no larger than $$100$$, followed by $$K$$ lines of sequences, each contains a permutationof the $$N_v$$ vertices. It is assumed that the first vertex is the source for each sequence. All the inputs in a line are separated by a space. ### Output Specification: For each of the $$K$$ sequences, print in a line `Yes` if it is a Dijkstra sequence, or `No` if not. ### Sample Input: ```in 5 7 1 2 2 1 5 1 2 3 1 2 4 1 2 5 2 3 5 1 3 4 1 4 5 1 3 4 2 5 3 1 2 4 2 3 4 5 1 3 2 1 5 4 ``` ### Sample Output: ```out Yes Yes Yes No ``` ### 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.