## 10099 - The Tourist Guide

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tri_ipst
New poster
Posts: 1
Joined: Wed Oct 19, 2016 5:30 pm

### Re: 10099 - The Tourist Guide

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
New poster
Posts: 15
Joined: Tue Oct 21, 2014 4:08 pm
Location: Bangladesh
Contact:

### Re: 10099 - The Tourist Guide

removed after accepted