119.使用邻接矩阵存储图
图结构,普及-
试题列表
  • 题目详情
  • 详情
  • 测评详情

有一个有向图，有n个顶点m条边，请使用邻接矩阵存储这个图，并输出这个图的邻接矩阵。如果如果两个点之间有多条边则邻接矩阵中只保存最短的边。如果两点之间没有边则输出999999999

输出格式
输入文件第一行包含一个正整数 N 和 M； 接下来 M 行， 每行三个正整数 U、 V、 W， 表示该条道路为从 U 到 V 的， 且通过这条道路 需要 W 的时间。满足 1≤U， V≤N,1≤W≤10000, 输入保证任意两点都能互相到达。
输出格式
一个n*n的矩阵，。矩阵的i行j列表示第i号城市和j号城市之间直接通路的时间。
限制:
对于 30%的数据，满足 1≤N≤200。 对于 100%的数据，满足 1≤N≤1000,1≤M≤100000。
样例:

输入

5 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 -1 5 4 2

输出

0 8 8 999999999 5 999999999 0 5 999999999 999999999 999999999 999999999 0 999999999 -1 8 999999999 999999999 0 3 999999999 999999999 4 2 0
0.044818s