地图

成绩 100 开启时间 2020年06月17日 星期三 18:00
折扣 0.8 折扣时间 2020年06月17日 星期三 18:00
允许迟交 是 关闭时间 2020年06月17日 星期三 18:00
输入文件 map.in 输出文件 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。