#1194. 【模板】Floyd
【模板】Floyd
说明
给出一张由 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个点 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>m 条边组成的无向图。
求出所有点对 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>�</mi><mo separator="true">,</mo><mi>�</mi><mo stretchy="false">)</mo></mrow></semantics></math>(i,j) 之间的最短路径。
输入格式
第一行为两个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo separator="true">,</mo><mi>�</mi></mrow></semantics></math>n,m,分别代表点的个数和边的条数。
接下来 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>m 行,每行三个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo separator="true">,</mo><mi>�</mi><mo separator="true">,</mo><mi>�</mi></mrow></semantics></math>u,v,w,代表 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo separator="true">,</mo><mi>�</mi></mrow></semantics></math>u,v 之间存在一条边权为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>w 的边。
输出格式
输出 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 行每行 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个整数。
第 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>i 行的第 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>j 个整数代表从 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>i 到 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>j 的最短路径。
如果两点间不存在路径,输出-1
样例
4 4
1 2 1
2 3 1
3 4 1
4 1 1
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0
提示
对于 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>100</mn><mi mathvariant="normal">%</mi></mrow></semantics></math>100% 的数据,<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo>≤</mo><mn>100</mn></mrow></semantics></math>n≤100,<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo>≤</mo><mn>4500</mn></mrow></semantics></math>m≤4500,任意一条边的权值 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>w 是正整数且 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>⩽</mo><mi>�</mi><mo>⩽</mo><mn>1000</mn></mrow></semantics></math>1⩽w⩽1000。
数据中可能存在重边。