https://acm.cs.nthu.edu.tw/problem/11922/

11922 - Shortest paths (電機班)   
Status  |  Limits 
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
Sample Input  

5
0 2 0 3 0
0 0 0 8 0
0 2 0 0 7
0 6 0 0 0
1 0 0 0 0
Show-path


Sample Output  

Path(0,1):0->1
Cost:2
Path(0,3):0->3
Cost:3
Path(1,3):1->3
Cost:8
Path(2,0):2->4->0
Cost:8
Path(2,1):2->1
Cost:2
Path(2,3):2->1->3
Cost:10
Path(2,4):2->4
Cost:7
Path(3,1):3->1
Cost:6
Path(4,0):4->0
Cost:1
Path(4,1):4->0->1
Cost:3
Path(4,3):4->0->3
Cost:4

Tags



Discuss



Contact us: nthucsoj@gmail.comc NTHU Online Judge 2015, Templates are from Bootswatch Project2018/5/14 23:44:44