// Arup Guha
// 8/22/03
// Solution to Gas Tank Problem for Local Programming Contest on 9/6/03.
#include <iostream.h>
#include <fstream.h>
#include <math.h>


double round(double x);
double min(double x, double y);

void main() {

  // Set up proper output precision.
  cout.setf(ios::fixed);
  cout.setf(ios::showpoint);
  cout.precision(2);

  int i, j, k, cnt;
  ifstream fin("gastank.in");  

  // Read in each input set.
  int setcnt = 1;

  while (true) {

    // Read in number of gas stations, gallons/tank and miles/gallon.
    int n, num_gal, mile_per_gal;
    fin >> n >> num_gal >> mile_per_gal;

    // Don't process the terminating case.
    if (n == 0 && num_gal == 0 && mile_per_gal == 0)
      break;

    int adj[50][50];
    double price[50];

    // Read in all the distances between gas stations and gas prices.
    for (i=0; i<n; i++) {
      for (j=0; j<n; j++) 
        fin >> adj[i][j];
      
      fin >> price[i];
    }

    cout << "Data set #" << setcnt << ":" << endl;

    // Read in number of cases to process with this graph.
    int numtrips, tripcnt;
    fin >> numtrips;
    for (tripcnt=1; tripcnt<=numtrips; tripcnt++) {

      // Read in start and finish gas stations and adjust for off by one.
      int start, finish;
      fin >> start >> finish;
      start--;
      finish--;

      // Fill in costs of travel to each location.
      double cost[50][50];    
      int tank = num_gal*mile_per_gal;
      for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {

          // Same gas station.
          if (i == j)
            cost[i][j] = 0;

          // Can't reach from station i to station j.
          else if (tank < adj[i][j])
            cost[i][j] = 10001;

          // Normal case.
          else {

            // If we're finishing, we don't have to fill up again.
            if (j == finish)
              cost[i][j] = 0;

            // Calculate cost per gallon needed to fill up.
            else
              cost[i][j] = 1.0*adj[i][j]/mile_per_gal*price[j];
          }
        }
      }

      //Adjust for fractional cent costs for each possible trip segement.
      for (i=0; i<n; i++) 
        for (j=0; j<n; j++) 
          cost[i][j] = round(cost[i][j]);        

      // Run Floyd-Warshall's on the adjusted graph.
      // Note: Dijksta's would be more efficient based on the given
      //       restrictions, but Floyd's is easier to code.
      for (k=0; k<n; k++)
        for (i=0; i<n; i++)
          for (j=0; j<n; j++)
            cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);

      cout << "   Trip #" << tripcnt << ":" << endl;
      cout << "      Starting gas station: " << (start+1) << endl;
      cout << "      Ending gas station: " << (finish+1) << endl;

      // If the cost is greater than 10000, no path was found.
      if (cost[start][finish] < 10000) {
        cout << "      The minimum cost for gas is $"; 
        cout << cost[start][finish] << "." << endl;
      }
      else 
        cout << "      The trip is impossible to complete." << endl;


    }  // end for tripcnt loop

    // Make adjustments for new set.
    cout << endl;
    setcnt++;

  } // end while(true)

}

double round(double x) {
  x = x + 0.005;
  x = 100*x;
  int temp = (int)floor(x);
  return temp/100.0;
}

double min(double x, double y) {
  if (x<y)
    return x;
  else
    return y;
}