2058: 最短路径问题

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：17 Solved：14

Description

暑假快到了，乐乐准备去一些城市旅行，其中有些城市之间有公路，有些城市之间则没有公路,如下图所示。为了节省经费以及方便计划旅程,小童希望在出发之前知道任意两个城市之间的最短路程。

Input

第一行为两个整数n,m(0<n<=10) ,接下来为m行,每行三个整数p、q、t，表示顶点 p 到顶点 q 的路程为t。

Output

 n行n列矩阵，表示任意两点之间的最短路径。

Sample Input Copy 

4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12

Sample Output Copy 

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