zoj 1456 Minimum Transport Cost

zoj 1456 Minimum Transport Cost

#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;    }