2003年加拿大计算机竞赛，第一阶段；为什么我的解决方案无效？

Question

我正在做加拿大计算机竞赛的旧版本，在一个网站上，我可以运行我的解决方案针对一些测试用例。我失败了他们的一个测试用例，但我想不出原因。我无法访问测试用例。

我在下面贴出了完整的问题描述，以及我在C++中尝试的解决方案。

问题

你是一个销售卡车的销售人员，它可以运载卡车，也可以运载卡车。不用说，你的卡车很重。此外，不用说，你必须驾驶这些卡车中的一辆穿过一个广阔的潮湿的领域，因为它是湿的，你需要驾驶一些桥梁。事实上，在两座城市之间的每条道路上，都有一座桥，但并不是每一座城市之间都有一条直接的道路。

每座桥都能承受一定的最大重量。这个最大权重是从0到100,000之间的整数。

你已经收到了一份城市名单，其中有顾客渴望看到你的一辆卡车。这些城市被称为目的地城市。既然你必须决定你要开哪辆卡车穿过这些城市，你将不得不回答以下问题:通过这些目的地城市的最大重量是多少？你要写一个程序来解决这个问题。

输入

第一行输入将包含三个正整数: c、r和d，分别指定城市数量(总计)、城市之间的道路数和目的地城市的数量。这些城市的数量从1到c，最多有10,000个城市，最多有100,000条道路。

下一条r线包含三倍的y_ w，表示这条路在城市x和y城市之间行驶，它的最大重量容量为w。接下来的d线给出了你必须用卡车访问的目的地城市。至少会有一个目的地城市。

您可以假设您从城市1开始，而该城市1不是目的地城市。您可以按任何顺序访问d目的地城市，但您必须访问所有d目的地城市。

输出

程序的输出是一个整数，最大的权重可以通过所有的d目标城市驱动。

样本输入

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

样本输出

30

我的解决方案

#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;
}

Answer 1

据我所知，阻止代码生成有效输出的唯一方法是getRoads中的一行。在加载输入时，您的代码保存了两个点之间的最低权重，而不是最高值。

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

相反，应：

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

认为这是唯一的问题的建议是基于测试用例贴在这里和假设我正确地遵循了代码中的算法。

非主题奖金备注：

memset按字节工作，而不是--例如--每个int。由于在此解释的原因，它在代码中工作，即：

• 0是一个异常，因为如果将所有字节设置为0，则该值将为零。
• -1是另一个例外，因为，正如Patrick突出显示的，-1在int8_t中是0xff (=255)，在int32_t中是0 0xffffffff。

循环数组并为非字节大小的对象初始化每个对象是更安全的。