Minimum Transport Cost

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

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

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;

const int maxn=50+10;
int dis[maxn][maxn],path[maxn][maxn],n,cost[maxn];
int u,st,en;

void floyd()
{
    for(int k=1;k<=n;k++)
      for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        int tmp=dis[i][k]+dis[k][j]+cost[k];
        if(tmp<dis[i][j]||(tmp==dis[i][j]&&path[i][j]>path[i][k]))
        {
            dis[i][j]=tmp;
            path[i][j]=path[i][k];
        }
    }
}

void read_Graph()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        scanf("%d",&u);
        if(u==-1)
            dis[i][j]=INF;
        else
        {
            dis[i][j]=u;
            path[i][j]=j;
        }
    }
    for(int i=1;i<=n;i++)
       scanf("%d",&cost[i]);
}

void solve()
{
    while(~scanf("%d%d",&st,&en))
    {
        if(st==-1&&en==-1)  break;
        printf("From %d to %d :\n",st,en);
        printf("Path: %d",st);
        int Gery=st;
        while(Gery!=en)
        {
            printf("-->%d",path[Gery][en]);
            Gery=path[Gery][en];
        }
        printf("\nTotal cost : %d\n\n",dis[st][en]);
    }
}

int main()
{
    while(~scanf("%d",&n),n)
    {
        read_Graph();
        floyd();
        solve();
    }
    return 0;
}