0
\$\begingroup\$

I am doing old versions of the Canadian Computing Competition, on a website where I can run my solution against some test cases they have. I am failing one of their test cases, and cannot figure out why. I have no access to the test case.

I have posted below the full problem description as well as my attempted solution in C++.

The Problem

You are a salesperson selling trucks which can carry trucks which can carry trucks. Needless to say, your trucks are heavy. Also needless to say, you have to drive one of these trucks across a wide wet domain, and since it is wet, you need to drive over some bridges. In fact, on every road between two cities, there is a bridge but there is not a direct road between every pair of cities.

Each bridge can support a certain maximum weight. This maximum weight is an integer from 0 to 100,000.

You have been given a list of cities where there are customers who are eager to view one of your trucks. These cities are called destination cities. Since you must decide which truck you will drive through these cities, you will have to answer the following problem: what is the maximum weight that can be driven through these destination cities? You are to write a program to solve this problem.

Input

The first line of input will contain three positive integers: c, r and d specifying the number of cities (in total), number of roads between cities and number of destination cities, respectively. The cities are numbered from 1 to c. There are at most 10,000 cities and at most 100,000 roads.

The next r lines contain triples x y w indicating that this road runs between city x and city y and it has a maximum weight capacity of w. The next d lines give the destination cities you must visit with your truck. There will be at least one destination city.

You can assume that you are starting in city 1 and that city 1 is not a destination city. You can visit the d destination cities in any order, but you must visit all d destination cities.

Output

The output from your program is a single integer, the largest weight that can be driven through all d destination cities.

Sample Input

5 7 3
1 2 20
1 3 50
1 4 70
1 5 90
2 3 30
3 4 40
4 5 60
2
4
5

Sample Output

30

My Solution

#include <stdio.h>
#include <string.h>
using namespace std;

const int MAX_WEIGHT = 100000;

/**
  * Extremely basic implementation of a min function.
  */
int min (int a, int b) {
    return a < b ? a : b;
}

void getRoads (int** M, int numRoads) {
    int weight, r; // weights and road indices are int
    unsigned short from, to; // city indices are u_short

    for (r = 0; r < numRoads; r++) {
        scanf ("%hu %hu %d", &from, &to, &weight);

        // deals with case of parallel edges
        if (M [from - 1][to - 1] < 0 || weight < M [from - 1][to - 1]) {
            // since all this shit is indexed from 1
            M [from - 1][to - 1] = weight;
            M [to - 1][from - 1] = weight;
        }
    }
}

void getDest (bool* dest, unsigned short numDest) {
    unsigned short c, d;

    for (c = 0; c < numDest; c++) {
        scanf ("%hu", &d);

        // still indexed from 1
        dest[d - 1] = true;
    }
}

int tally (int* A, bool* dest, unsigned short numCities) {
    int m = MAX_WEIGHT + 1;

    for (unsigned short c = 0; c < numCities; c++) {
        if (dest[c] && A[c] < m) {
            m = A[c];
        }
    }

    return m;
}

int main () {
    int numRoads, next; // using int for weights and road indices
    unsigned short numCities, numDest, c, c2; // using u_short for cities

    scanf("%hu %d %hu", &numCities, &numRoads, &numDest);

    if (numDest > numCities) {
        // invalid input
        return 1;
    }

    if (numDest == 0) {
        // trivial case
        printf("0\n");
        return 0;
    }

    // create Matrix
    int** M = new int* [numCities];
    for (c = 0; c < numCities; c++) {
        M[c] = new int [numCities];
        memset(M[c], -1, numCities * sizeof(int));
    }

    getRoads (M, numRoads);

    // create destination array
    // for each city c, true iff c is a destination
    bool dest [numCities];
    memset (dest, false, numCities);
    getDest (dest, numDest);

    // create dynamic programming array
    // keeps a record of smallest weight to each city
    int A [numCities]; 
    memset (A, 0, numCities * sizeof (int));

    // implementing a set in N + 1 bits.
    // updated vertices are flagged with a 1
    // isEmpty set to true at beginning of pass, then if true at end of pass, is really empty
    bool isEmpty = false;
    bool Q [numCities];
    memset(Q, false, numCities);
    Q[0] = true;

    while (! isEmpty) {
        isEmpty = true;

        for (c = 0; c < numCities; c++) {

            if (! Q[c]) {
                continue;
            } else {
                Q[c] = false;
            }

            // don't look at edges which lead back to origin
            for (c2 = 1; c2 < numCities; c2++) {
                if (c == c2 || M[c][c2] < 0) continue;

                // only happens when c == 0 (hopefully)
                if (A[c] == 0) {
                    next = M [c][c2];
                } else {
                    next = min(M [c][c2], A[c]);
                }

                if (next > A[c2]) {
                    A [c2] = next;
                    Q[c2] = true;
                    isEmpty = false;
                }
            }
        }
    }

    printf("%d\n", tally (A, dest, numCities));

    return 0;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ I've voted to keep this open despite @BlackSheep's admission that it gives incorrect results, because it does give the correct output for the sample input. According to the Help Center, "correctness in unanticipated cases" is on-topic. \$\endgroup\$ – 200_success Oct 5 '13 at 18:47
2
\$\begingroup\$

As far as I can tell, the only thing blocking your code from producing valid output is one line in getRoads. When loading the input, your code saves the lowest weight between two points rather than the highest.

    if (M [from - 1][to - 1] < 0 || weight < M [from - 1][to - 1]) {

should instead be:

    if (weight > M [from - 1][to - 1]) {

The suggestion that this was the only problem is based on the test cases posted here and the assumption that I followed the algorithm in your code correctly.


Off-Topic Bonus Note:

memset works per byte, not - for example - per int. It works in your code for reasons explained here, namely:

  • 0 is an exception since, if you set all the bytes to 0, the value will be zero
  • -1 is another exception since, as Patrick highlighted -1 is 0xff (=255) in int8_t and 0xffffffff in int32_t

It is safer to loop over the array and initialize each object for non byte-sized objects.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.