Pro.ID1543 TitleMinimum Transport Cost Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1543 AC2 Submit4 Ratio50.00% 时间&空间限制描述These are N cities in Spring country. Between each pair of cities there may be one transportation track or none. Now there is some cargo that should be delivered from one city to another. The transportation fee consists of two parts:
You must write a program to find the route which has the minimum cost. 输入First is N, number of cities. N = 0 indicates the end of input. The data of path cost, city tax, source and destination cities are given in the input, which is of the form: a11 a11 ... a1N where aij is the transport cost from city i to city j, aij = -1 indicates there is no direct path between city i and city j. bi represents the tax of passing through city i. And the cargo is to be delivered from city c to city d, city e to city f, ..., and g = h = -1. You must output the sequence of cities passed by and the total cost which is of the form. 输出Description These are N cities in Spring country. Between each pair of cities there may be one transportation track or none. Now there is some cargo that should be delivered from one city to another. The transportation fee consists of two parts:
You must write a program to find the route which has the minimum cost. Input First is N, number of cities. N = 0 indicates the end of input. The data of path cost, city tax, source and destination cities are given in the input, which is of the form: a11 a11 ... a1N where aij is the transport cost from city i to city j, aij = -1 indicates there is no direct path between city i and city j. bi represents the tax of passing through city i. And the cargo is to be delivered from city c to city d, city e to city f, ..., and g = h = -1. You must output the sequence of cities passed by and the total cost which is of the form. Output From c to d : Sample Input 5 Sample Output From 1 to 3 : Source 样例输入5 样例输出From 1 to 3 : 作者 |