#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>#include <algorithm>using namespace std;int N;int G[1005][1005]; int path[1005][1005]; int dis[1005]; int add[1005]; void floyd() { int reca[1005], recb[1005], idxa, idxb; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { path[i][j] = j; } } for (int k = 1; k <= N; ++k) { for (int i = 1; i <= N; ++i) { if (i == k || G[i][k] == -1) continue; for (int j = 1; j <= N; ++j) { if (j == k || G[k][i] == -1) continue; if (G[i][k] != -1 && G[k][j] != -1) { if(G[i][j] > G[i][k] + G[k][j] || G[i][j] == -1) { G[i][j] = G[i][k] + G[k][j]; path[i][j] = path[i][k]; } else if (G[i][j] == G[i][k] + G[k][j]) { if (path[i][j] > path[i][k]) { path[i][j] = path[i][k]; } } } } } }}void display(int x, int y) { if (x != y) { printf("-->%d", path[x][y]); display(path[x][y], y); }}int main() { while (cin >> N, N) { memset(path, 0xff, sizeof (path)); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { scanf("%d", &G[i][j]); } } for (int i = 1; i <= N; ++i) { scanf("%d", &add[i]); } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { if (i == j || G[i][j] == -1) continue; else G[i][j] += add[j]; } } floyd(); int a, b, first; while (scanf("%d %d", &a, &b), a!=-1 && b!=-1) { first = 1; printf("From %d to %d :n", a, b); printf("Path: %d", a); display(a, b); puts(""); printf("Total cost : %dnn", a!=b ? G[a][b]-add[b] : 0); } } return 0; }
