1467 - 電機系 (呂老師) DS 上機考4

#	Problem	Pass Rate (passed user / total user)
11936	(電機班上機考) The Cost of Shortest Paths

11936 - (電機班上機考) The Cost of Shortest Paths

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB
Case 5	1 sec	32 MB

Description

Given

Number of matrix
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
Print out the cost of shortest path of each pair of nodes

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
Take the following figure as an example

Output

Print out the cost for each pair in row major order.
Print a new line between matrices.

Sample Input Download

3
3
0 5 1 
0 0 3 
6 0 0 
5
0 4 1 0 8 
0 0 0 8 8 
5 8 0 6 9 
0 0 0 0 6 
0 2 4 9 0 
7
0 0 0 8 3 5 5 
4 0 5 2 5 0 4 
3 0 0 6 0 9 0 
7 6 0 0 3 1 0 
8 5 5 0 0 0 0 
4 0 0 9 9 0 6 
0 6 3 0 2 9 0

Sample Output Download

Cost(0,1):5
Cost(0,2):1
Cost(1,0):9
Cost(1,2):3
Cost(2,0):6
Cost(2,1):11

Cost(0,1):4
Cost(0,2):1
Cost(0,3):7
Cost(0,4):8
Cost(1,0):17
Cost(1,2):12
Cost(1,3):8
Cost(1,4):8
Cost(2,0):5
Cost(2,1):8
Cost(2,3):6
Cost(2,4):9
Cost(3,0):15
Cost(3,1):8
Cost(3,2):10
Cost(3,4):6
Cost(4,0):9
Cost(4,1):2
Cost(4,2):4
Cost(4,3):9

Cost(0,1):8
Cost(0,2):8
Cost(0,3):8
Cost(0,4):3
Cost(0,5):5
Cost(0,6):5
Cost(1,0):4
Cost(1,2):5
Cost(1,3):2
Cost(1,4):5
Cost(1,5):3
Cost(1,6):4
Cost(2,0):3
Cost(2,1):11
Cost(2,3):6
Cost(2,4):6
Cost(2,5):7
Cost(2,6):8
Cost(3,0):5
Cost(3,1):6
Cost(3,2):8
Cost(3,4):3
Cost(3,5):1
Cost(3,6):7
Cost(4,0):8
Cost(4,1):5
Cost(4,2):5
Cost(4,3):7
Cost(4,5):8
Cost(4,6):9
Cost(5,0):4
Cost(5,1):12
Cost(5,2):9
Cost(5,3):9
Cost(5,4):7
Cost(5,6):6
Cost(6,0):6
Cost(6,1):6
Cost(6,2):3
Cost(6,3):8
Cost(6,4):2
Cost(6,5):9

1467 - 電機系 (呂老師) DS 上機考4 Scoreboard

Time

Clarification

11936 - (電機班上機考) The Cost of Shortest Paths

Description

Input

Output

Sample Input Download

Sample Output Download

Tags

Discuss