10099 - The Tourist Guide

[tri_ipst]

I can't figure out why I'm getting WA. The code generates the indicated results for the example in the problem description, the example earlier in this thread with answer 0, and the input from Morass on uDebug.

It is as follows:

Code: Select all

// Solve the Tourist Guide Problem
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <vector>
#include <climits>
#include <algorithm>

const int LARGE_VALUE = INT_MAX;
const int SMALL_VALUE = INT_MIN;
const int SPCL_VALUE = SMALL_VALUE;
const int MIN_INDEX = 1;
int MIN_POWER_NEEDED = 100;

#define MAX_LINE_SIZE 1000000
int getFldsFromLine(char *line, std::vector<char *> &res, const char* sep = " \t\n\v\f\r");

#define mallocOrDie(name, num, type) name = (type *) calloc (num, sizeof ( type )); \
if (name == NULL) { fprintf (stderr, "Couldn't allocate space for '%s'\nBye!\n", #name ); exit (-1); }

#define makeArray(name, m, n, type) if (name != NULL) { free (name[0]); free (name); } if ((n)*(m) == 0) { name = NULL; } else {mallocOrDie (name, (m), type *); \
mallocOrDie (name[0], ((m)*(n)), type); for (int fdsafdas=0; fdsafdas<m-1; ++fdsafdas) { name[fdsafdas+1] = name[fdsafdas] + (n); } }

int main (int argc, char **argv)
{
     FILE *infile = stdin;
//     infile = fopen ("inputs/problem10099.txt", "r");
     int maxIndex = 1000;
     int **arr = NULL, **arr2 = NULL;
     char line[MAX_LINE_SIZE];
     std::vector<char *> flds;
     int numFlds, numCases, caseNum=0;
     makeArray (arr, maxIndex+1, maxIndex+1, int);
     makeArray (arr2, maxIndex+1, maxIndex+1, int);
     while (fgets (line, MAX_LINE_SIZE, infile)) {
          numFlds = getFldsFromLine (line, flds);
          int N = atoi (flds[0]), R = atoi (flds[1]);
          maxIndex = N;
          if ((!N) && (!R))
               break;
          ++caseNum;
          // Initialize arr vector
          for (int i=MIN_INDEX; i<=maxIndex; ++i)
               for (int j=MIN_INDEX; j<=maxIndex; ++j)
                    if (i == j)
                         arr[i][j] = INT_MAX;
                    else
                         arr[i][j] = 0;
          // Now read in the data and put it in the appropriate elements
          // Now squaring the vector
          for (int i=0; i<R; ++i) {
               fgets (line, MAX_LINE_SIZE, infile);
               numFlds = getFldsFromLine (line, flds);
               int num1 = atoi (flds[0]), num2 = atoi (flds[1]), weight = atoi (flds[2]);
               arr[num1][num2] = arr[num2][num1] = weight; }
          for (int power = 1; power <= MIN_POWER_NEEDED; power *= 2) {
               // Initialize arr2
               for (int i=MIN_INDEX; i<=maxIndex; ++i)
                    for (int j=MIN_INDEX; j<=maxIndex; ++j)
                         arr2[i][j] = 0;
               // "Square" arr to get arr2
               for (int i=MIN_INDEX; i<=maxIndex; ++i)
                    for (int j=MIN_INDEX; j<=maxIndex; ++j) {
                         for (int k=MIN_INDEX; k<=maxIndex; ++k) {
                              int newValue = std::min(arr[i][j], arr[j][k]);
                              arr2[i][k] = std::max (arr2[i][k], newValue);
                         }
                    }
               // copy arr2 to arr
               for (int i=MIN_INDEX; i<=maxIndex; ++i)
                    for (int j=MIN_INDEX; j<=maxIndex; ++j)
                         arr[i][j] = arr2[i][j];
          }
          fgets (line, MAX_LINE_SIZE, infile);
          numFlds = getFldsFromLine (line, flds);
          int begin = atoi (flds[0]), end = atoi (flds[1]), passengers = atoi (flds[2]);
          printf ("Scenario #%d\n", caseNum);
          int maxOnSingleTrip = arr[begin][end]-1;
          int numTrips = passengers / maxOnSingleTrip;
          if (passengers % maxOnSingleTrip != 0)
               ++numTrips;
          if (begin == end)
               numTrips = 0;
          printf ("Minimum Number of Trips = %d\n", numTrips);
          printf ("\n");
     }

     makeArray (arr, 0, 0, int);
     makeArray (arr2, 0, 0, int);

     return (0);
}

int getFldsFromLine(char *line, std::vector<char *> &res, const char* sep) {
  char *saveptr;
  res.clear();

  char *tok = strtok_r(line, sep, &saveptr);
  while(tok) {
    res.push_back(tok);
    tok = strtok_r(0, sep, &saveptr);
  }
  return res.size();
}

Any help would be appreciated. Thanks very much.

[Helaluddin_brur]

removed after accepted