Referência para GPS I Love You (LA 5785)

#include <stdio.h>
#include <algorithm>
using namespace std;

const int inf =0x3f3f3f3f;

int n;
int g[110][110];
int d[110][110];
int m;
int p[110];
int _42=1;

int main() {
    while (1) {
        scanf("%d", &n);
        if (!n) break;

        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++) {
                scanf("%d", &g[i][j]);
                if (g[i][j]==0 && i!=j) g[i][j]=inf;
            }

        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                d[i][j]=g[i][j];

        for (int k=0; k<n; k++)
            for (int i=0; i<n; i++)
                for (int j=0; j<n; j++)
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

        scanf("%d", &m);

        for (int i=0; i<m; i++)
            scanf("%d", &p[i]);

        int src=p[0];
        int force=0;

        for (int i=1; i<m; i++)
            if (d[src][p[i]]<d[src][p[i-1]]+g[p[i-1]][p[i]])
                force++, src=p[i];

        printf("Case %d: %d\n", _42++, force);
    }

    return 0;
}