#A. 多源最短路

    传统题 2000ms 128MiB

多源最短路

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

n{n} 个 城市,从1{1}n{n}给他们编号,它们之间由一些单向道路(即一条道路只能从一个方向走向另一个方向,反之不行)相连,每条路还有一个花费c(i){c(i)},表示通过第i条边需要花费c(i){c(i)}的时间。

求任意两点间的最快路径

输入格式

第一行一个整数n{n},表示有多少个城市和多少条道路。

接下来nn行,每行nn个整数

i+1{i+1}行第j{j}个数xx表示从i{i}j{j}有一条花费为xx的边。(第i+1{i+1}行第i{i}个数为0{0}

输出格式

n n行,每行n n个整数

i i行第j j个数表示从i ij j最少需要多少时间。(第i i行第i i个数为0{ 0 }

样例

输入样例

4
0 487 569 408 
705 0 306 357 
95 222 0 618 
961 401 688 0

输出数据

0 487 569 408 
401 0 306 357 
95 222 0 503 
783 401 688 0

数据范围与提示

100%{ 100\%}的数据,1n500{1\le n\le 500}

0mn(n1){ 0\le m\le n*(n-1) }

星哲-最短路

未认领
状态
已结束
题目
5
开始时间
2023-5-21 0:00
截止时间
2023-5-31 23:59
可延期
24 小时