Floyd Warshall Path Printing

#include <iostream>

#include <cstdio>

#include <map>

#include <vector>

using namespace std;

#define siz 1001

#define INF 10000000

int a[siz][siz],path[siz][siz];

map <char,int> mp;

map <int,char> pa;

vector <int> temp;

int n,m;

void reset(int n){

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

        for(int j=0;j<=n;j++){

            if(i==j){

                a[i][j]=0;

                path[i][j]=-1;

            }

            else{

                a[i][j]=INF;

                path[i][j]=i;

            }

        }

    }

}

void floyd_warshall(){

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

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

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

                if(a[i][j]>(a[i][k]+a[k][j])){

                    a[i][j]=(a[i][k]+a[k][j]);

                    path[i][j]=path[k][j];

                }

            }

        }

    }

}

void path_print(int s,int t)

{

    if(path[s][t]==s) temp.push_back(s);

    else {

        path_print(s,path[s][t]);

        path_print(path[s][t],t);

    }

}



int main()

{

    int cost,q;

    char u,v;

    #ifndef ONLINE_JUDGE

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

    #endif

    while(scanf("%d%d",&n,&m)==2){

        reset(n);

        int index=1;

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

            cin>>u>>v>>cost;

            if(mp[u]==0){

                mp[u]=index;

                pa[index]=u;

                index++;

            }

            if(mp[v]==0){

                mp[v]=index;

                pa[index]=v;

                index++;

            }

            a[mp[u]][mp[v]]=a[mp[v]][mp[u]]=cost;

        }

        floyd_warshall();

        scanf("%d",&q);

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

            cin>>u>>v;

            int x,y;

            x=mp[u];

            y=mp[v];

            path_print(x,y);

            for(int j=0;j<temp.size();j++){

                if(j!=0) printf(" ");

                printf("%c",pa[temp[j]]);

            }

            printf(" %c\n",pa[y]);

            temp.clear();

        }

        mp.clear(); pa.clear();

    }

    return 0;

}