Rejudge Progress:

2478: 最短路问题

Time Limit: 5000 MS Memory Limit: 65536 KB
Total Submit: 53 Accepted: 18 Page View: 443
Submit Status Discuss
现在有n个城市,编号从1到n。现在已知从城市i到城市j需要走的时间为aij。M78要从城市1到城市n。M78有一个飞行符,飞行符可以使得他瞬间通过一条边或连续的两条边(连续走一条边或两条边的时间为0)。问,M78从城市1到城市n,最少花费的时间。
多组输入。每组第一行有一个整数n,表示城市的数目。(2<=n<=1000) 接下来将输入一个n*n的矩阵。矩阵第i行第j列的数字aij表示从城市i到城市j,花费的时间为aij。(0<=aij<=10000 , aii=0 ,aij=aji)。如果aij=0,表示没有这条路。
每组输出一个数字,表示M78从城市1到城市n花费的最少时间。特别的,如果M78到不到了城市n,输出-1。
3 0 1 1 1 0 1 1 1 0