Description
- Given
- A matrix of digits
- Task
- Convert the nonzero digits of the matrix into a graph
- The nonzero digits represent the weights of edges between two nodes
- The last line can be either "Show-path" or "Hide-path"
- If the last line is "Show-path", print out the shortest path of each pair of nodes
- If the last line is "Hide-path", leave the printed shortest path (e.g., "1->2->3->4->5") empty
- 測資 1 就是 sample input/output
- 測資 2~8 是 "Hide-path" (比較簡單)、測資 9~10 是 "Show-path"
Input
Matrix Specification
- Each cell in the matrix contains a digit value (ranged from 0 to 9)
- 0 represents no edge between two nodes
- Nonzero digits represents the weights of two node
- 100≥ Number of vertices (i.e., matrix width and height) ≥2
Output
- Print out the shortest path with row major order and the corresponding cost for each pair
- If the cost of the two paths are equivalent, select the one which the path string is smaller.
- EX:
path A: 1->2->3->4->5
path B: 1->3->2->4->5
path C: 1->4->5
You need to print out path A.
If the last line is "Hide-path", leave the printed shortest path (e.g., "1->2->3->4->5") empty
- EX: