Minimum Transport Cost

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6044 Accepted Submission(s): 1527

Problem 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:
The cost of the transportation on the path between these cities, and

a certain tax which will be charged whenever any cargo passing through one city, except for the source and the destination cities.

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 a12 ... a1N
a21 a22 ... a2N
...............
aN1 aN2 ... aNN
b1 b2 ... bN

c d
e f
...
g h

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 :
Path: c-->c1-->......-->ck-->d
Total cost : ......
......

From e to f :
Path: e-->e1-->..........-->ek-->f
Total cost : ......

Note: if there are more minimal paths, output the lexically smallest one. Print a blank line after each test case.

Sample Input

5
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4
-1 -1
0

Sample Output

From 1 to 3 :

Path: 1-->5-->4-->3

Total cost : 21

From 3 to 5 :

Path: 3-->4-->5

Total cost : 16

From 2 to 4 :

Path: 2-->1-->5-->4

Total cost : 17

　　题意：给你一些点以及不同点之间的有向边，其中每一条边都有一个权值代表经过这条边的时候需要花费一定的费用，同时每个顶点也有一个权值，代表经过这个点的时候需要花费一定的费用，给出一个起点一个终点，问从起点到终点最少需要多少费用，并且打印这条路径出来。

　　题目可以分解成两个问题，一是求最少费用，二是打印路径。

　　对于第一个问题，这里的询问可能会有很多，而且不是单源最短路，所以最好使用Flyod先把最短路都求出来，由于这里多了有顶点权值这一个值，所以松弛的判断要变成 dis[i][j]>dis[i][u]+dis[u][j]+tax[u] 。

　　然后第二个问题是打印路径，由于这里用的是Flyod，所以用来保存路径的数组要开成二维，path[i][j]代表的是要到达点j，当前在点i，那么下一个需要经过的点是path[i][j] (这里是看了人家的代码以后推测出来的)。也就是说起点a到终点b，一开始是在a，那么路径就是a-->path[a][b]-->···-->path[i][b]-->b,其中i是它的前一项path[i][b]。这里一开始要初始化path[i][j]=j即从i开始出发到达j下一个点就是j，即一开始假设一步就可以到达目的地。

　　当然这里还需要判断是不是字典序最小，这里只需要松弛的时候再判断一下就可以了。

　　总的来说对于打印路径还不是很熟悉，尤其是Flyod的打印路径的方法，还需要加强。

代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#define INF 100000000
#define MAX 600
using namespace std;

int tax[MAX],dis[MAX][MAX],path[MAX][MAX],n;

void Flyod()
{
   int i,j,u;
   for(u=1;u<=n;u++)
   {
       for(i=1;i<=n;i++)
       {
           for(j=1;j<=n;j++)
           {
               int len=dis[i][u] + dis[u][j] + tax[u];
               if(dis[i][j]> len)
               {
                   path[i][j]=path[i][u];
                   dis[i][j]=len;
               }
               else if(dis[i][j]==len && path[i][j]>path[i][u])
               {
                   path[i][j]=path[i][u];
               }
           }
       }
   }
}

void print_path(int a,int b)
{
   int i;
   printf("Path: ");
   printf("%d",a);
   i=a;
   while(i!=b)
   {
       printf("-->");
       printf("%d",path[i][b]);
       i=path[i][b];
   }
   printf("
");
}

void Print(int a,int b)
{
   printf("From %d to %d :
",a,b);
   print_path(a,b);
   printf("Total cost : %d
",dis[a][b]);
}

int main()
{
   int i,j,len,a,b;
   //freopen("data.txt","r",stdin);
   while(scanf("%d",&n),n)
   {
       for(i=1;i<=n;i++)
       {
           for(j=1;j<=n;j++)
           {
               dis[i][j]= i==j ? 0 : INF;
               scanf("%d",&len);
              if(len!=-1) dis[i][j]=len;
               path[i][j]=j;
           }
       }
       for(i=1;i<=n;i++) scanf("%d",&tax[i]);
       Flyod();
       while(scanf("%d %d",&a,&b),(a!=-1 && b!=-1))
       {
           Print(a,b);
           printf("
");
       }
   }
   return 0;
}
1385