UVa 1247 - Interstar Transport

// UVa 1247 - Interstar Transport

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
using namespace std;

vector<char> sol;
char R['Z' + 1]['Z' + 1];
int D['Z' + 1]['Z' + 1];

void get_sol(char a, char b){
	if (D[a][b] == 1)
		sol.push_back(b);
	else {
		get_sol(a,R[a][b]);
		get_sol(R[a][b],b);
	}
}

int main() {
	int n, m;
	while (cin >> n >> m) {
		int lnk['Z' + 1]['Z' + 1];
		memset(lnk, 127, sizeof(lnk));

		memset(D, 127, sizeof(D));
		int oo = lnk[0][0];
		for (int i = 0; i < m; i++) {

			string a, b;
			int c;
			cin >> a >> b >> c;
			lnk[a[0]][b[0]] = c;
			lnk[b[0]][a[0]] = c;
			D[a[0]][b[0]] = 1;
			D[b[0]][a[0]] = 1;
			D[a[0]][a[0]] = 0;
			D[b[0]][b[0]] = 0;
		}
		// floyd
		for (int k = 'A'; k <= 'Z'; k++)
			for (int i = 'A'; i <= 'Z'; i++)
				if (lnk[i][k] != oo) {
					for (int j = 'A'; j <= 'Z'; j++)
						if (lnk[k][j] != oo && lnk[i][k] + lnk[k][j] < lnk[i][j]
								|| lnk[i][k] + lnk[k][j] == lnk[i][j]
										&& D[i][j] > D[i][k] + D[k][j]) {
							lnk[i][j] = lnk[i][k] + lnk[k][j];
							D[i][j] = D[i][k] + D[k][j];
							R[i][j] = k;
						}
				}
		// queries
		cin >> m;
		for (int i=0; i<m; i++){
			string a,b;
			cin >> a >> b;
			sol.clear();
			get_sol(a[0],b[0]);
			cout << a[0];
			for (int j=0; j<sol.size(); j++)
				cout << " " << sol[j];
			cout << endl;
		}

	}
	return 0;
}