Code: Select all
#include <iostream>
#include <cstring>
#include <iomanip>
#include <vector>
#include <utility>
using namespace std;
typedef pair<char, char> ii;
const int INF = 1 << 27;
const int MAXS = 30;
int S, P;
int graph[MAXS][MAXS];
int b[MAXS][MAXS];
int l[MAXS][MAXS];
vector<ii> queries;
void read()
{
queries.clear();
memset(b, -1, sizeof b);
memset(l, 0, sizeof l);
for(int i = 0; i < MAXS; ++i)
{
for(int j = 0; j < MAXS; ++j)
{
graph[i][j] = INF;
}
graph[i][i] = 0;
}
for(int i = 0; i < P; ++i)
{
char a, b;
int d;
cin >> a >> b >> d;
graph[a - 'A'][b - 'A'] = d;
graph[b - 'A'][a - 'A'] = d;
}
int N;
cin >> N;
for(int i = 0; i < N; ++i)
{
char from, to;
cin >> from >> to;
queries.push_back(ii(from, to));
}
}
void Floyd_Warshall()
{
for(int k = 0; k < MAXS; ++k)
{
for(int i = 0; i < MAXS; ++i)
{
for(int j = 0; j < MAXS; ++j)
{
if(i == j || i == k || j == k) continue;
if(graph[i][k] + graph[k][j] < graph[i][j])
{
graph[i][j] = graph[i][k] + graph[k][j];
b[i][j] = k;
l[i][j] = l[i][k] + l[k][j] + 1;
}
else if(graph[i][k] + graph[k][j] == graph[i][j] && l[i][k] + l[k][j] + 1 < l[i][j])
{
l[i][j] = l[i][k] + l[k][j] + 1;
b[i][j] = k;
}
}
}
}
}
void backtrack(int from, int to)
{
int intermidiate = b[from][to];
if(intermidiate == -1) return;
backtrack(from, intermidiate);
cout<<' '<<(char)(intermidiate + 'A');
}
void solve()
{
Floyd_Warshall();
for(int i = 0; i < queries.size(); ++i)
{
cout<<queries[i].first;
backtrack(queries[i].first - 'A', queries[i].second - 'A');
cout<<' '<<queries[i].second;
cout<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
while(cin >> S)
{
cin >> P;
read();
solve();
}
return 0;
}