地图

Grade 100 Open Time Wednesday, 17 June 2020, 6:00 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 6:00 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 6:00 PM
Input file map.in Output file map.out

【题目描述】地图(map)

有一张地图如图5.48所示。现在要从A点出发,找到一条最短的路径到其他各点,试编程解决该问题。

 

图5.48

 

【输入格式】

输入有若干行,第一行为一个整数n,表示共有n个地点。

随后n行,每行n个数,分别表示该地点与其他地点之间路线的长度,如果两点间没有路径则以-1表示。

【输出格式】

输出n行,每行一个整数,依次表示地点1到其他各点的最短路径。

【输入样例】

6

-1 6 3 -1 -1 -1

-1 -1 -1 5 -1 -1

-1 2 -1 3 4 -1

-1 -1 -1 -1 2 3

-1 -1 -1 -1 -1 5

-1 -1 -1 -1 -1 -1

【输出样例】

0

5

3

6

7

9

【数据规模】

对于40%的数据,保证有n<100;

对于60%的数据,保证有n<256;

对于全部的数据,保证有n≤1 501。