UVa1247

UVa1247
ワーシャルフロイドする。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

const int N = 30;
pair<int, int> g[N][N];

int path[N][N];
vector<int> buff;

void print_path(int i, int j)
{
  if (path[i][j] == -1) return ;
  print_path(i, path[i][j]);
  buff.push_back(path[i][j]);
  print_path(path[i][j], j);
  return ;
}

int main(int argc, char *argv[])
{
  int node, edge;
  while (cin >> node >> edge) {
    fill(&g[0][0], &g[N - 1][N], make_pair(1 << 28, 1 << 28));
    fill(&path[0][0], &path[N - 1][N], -1);
   
    for (int i = 0; i < edge; ++i) {
      char a, b;
      int c;
      cin >> a >> b >> c;
      a -= 'A';
      b -= 'A';
      g[a][b] = make_pair(c, 1);
      g[b][a] = make_pair(c, 1);
    }

    for (int k = 0; k < node; ++k) {
      for (int i = 0; i < node; ++i) {
        for (int j = 0; j < node; ++j) {
          pair<int, int> p;
          p.first = g[i][k].first + g[k][j].first;
          p.second = g[i][k].second + g[k][j].second;
          if (p < g[i][j]) {
            g[i][j] = p;
            path[i][j] = k;
          }
        }
      }
    }

    int q;
    cin >> q;
    while (q--) {
      char a, b;
      cin >> a >> b;
      buff.clear();
      print_path(a - 'A', b - 'A');
      cout << a ;
      for (int i = 0; i < buff.size(); ++i) {
        cout << ' ' << (char)(buff[i] + 'A');
      }
      cout << ' ' << b << endl;
    }

  }
  return 0;
}