All-Pairs Shortest Paths - (Floyd–Warshall)

#include <iostream>

#include <cstdio>

using namespace std;

#define  inf_max 21474836

#define  siz 1001

int a[siz][siz];

int c,s,q;



void reset (int c){

    for ( int i = 0; i <= c; i++ )

        for ( int j = 0; j <= c; j++ )

            a[i][j] = inf_max;

}



void floydWarshall(){

    for(int k=1;k<=c;k++){

        a[k][k]=0;

        for(int i=1;i<=c;i++){

            for(int j=1;j<=c;j++){

                a[i][j]=min(a[i][j],max(a[i][k],a[k][j]));

            }

        }

    }

}

int main()

{

   int c1,c2,dis,kas=1;

   #ifndef ONLINE_JUDGE

   freopen("input.txt","r",stdin);

   #endif

   while(scanf("%d%d%d",&c,&s,&q)==3){

       if(c==0&&s==0&&q==0) break;

       if(kas!=1) printf("\n");

       reset(c);

       for(int i=0;i<s;i++){

           scanf("%d%d%d",&c1,&c2,&dis);

           a[c1][c2]=a[c2][c1]=dis;

       }

        floydWarshall();

        printf("Case #%d\n",kas++);

        for(int i=0;i<q;i++){

            scanf("%d%d",&c1,&c2);

            if(a[c1][c2]==inf_max) printf("no path\n");

            else printf("%d\n",a[c1][c2]);

        }

    }

    return 0;

}