主观题：The 2nd-shortest Path
Holiday is coming. Lisa wants to go home by train. But this time, Lisa does not want to go home directly -- she has decided to take the second-shortest rather than the shortest path. Your job is to help her find the path.
There are $$M$$ stations and $$N$$ unidirectional railway between these stations. For simplicity Lisa starts at No.1 station and her home is at No.$$M$$ station.
The second-shortest path can **backtrack**, i.e., use the same road more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e. if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).
### Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers $$M$$ ($$1\le M \le 1000$$) and $$N$$ ($$1\le N\le 5000$$) which are specified in the above description. Then $$N$$ lines follow, each contains three space-separated integers: $$A$$, $$B$$, and $$D$$ that describe a road from $$A$$ to $$B$$ and has length $$D$$ ($$1 \le D \le 5000$$)
### Output Specification:
For each test case, print in one line the length of the second-shortest path between node 1 and node $$M$$, then followed by the nodes' indices in order. There must be exactly 1 space between the numbers, and no extra space at the beginning or the end of the line.
### Sample Input:
in
5 6
1 2 50
2 3 100
2 4 150
3 4 130
3 5 70
4 5 40
### Sample Output:
out
240 1 2 4 5
### 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.
There are $$M$$ stations and $$N$$ unidirectional railway between these stations. For simplicity Lisa starts at No.1 station and her home is at No.$$M$$ station.
The second-shortest path can **backtrack**, i.e., use the same road more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e. if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).
### Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers $$M$$ ($$1\le M \le 1000$$) and $$N$$ ($$1\le N\le 5000$$) which are specified in the above description. Then $$N$$ lines follow, each contains three space-separated integers: $$A$$, $$B$$, and $$D$$ that describe a road from $$A$$ to $$B$$ and has length $$D$$ ($$1 \le D \le 5000$$)
### Output Specification:
For each test case, print in one line the length of the second-shortest path between node 1 and node $$M$$, then followed by the nodes' indices in order. There must be exactly 1 space between the numbers, and no extra space at the beginning or the end of the line.
### Sample Input:
in
5 6
1 2 50
2 3 100
2 4 150
3 4 130
3 5 70
4 5 40
### Sample Output:
out
240 1 2 4 5
### 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.
