第36次csp认证第四题——跳房子runtime error

Question

小白想参加csp认证试一下，做了一下2024年12月的题目，第四题我用dijkstra最短路径，两个测试用例都是对的，但是交上去显示runtime error，想问一下好心人们我错在哪了怎么改啊，或者这道题有没有什么更好的做法（不知道官方题解有没有……）🙏🏻🙏🏻🙏🏻我不求全做对只求对几个用例骗点分就好了。。。

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 100010;
int h[N], e[N], idx, ne[N];
int n, a[N], k[N];
int d[N];
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        }
        for (int j = h[t]; j != -1; j = ne[j])
        {
            d[e[j]] = min(d[e[j]], d[t] + 1);
        }
        st[t] = true;
    }
    if (d[n] == 0x3f3f3f3f)
        return -1;
    return d[n];
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &k[i]);

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k[i] && i + j <= n; j++)
        {
            add(i, i + j - a[i + j]);
        }
    }
    printf("%d\n", dijkstra());
}

---

根据评论区的提示，我在add函数里加上了限制(同时我觉得可能也是N小了所以给扩了10倍)，顺利通过第一个子任务，第二三个子任务都是超时。为了减少一点时间，我换成了堆优化的dijkstra，目前是第一个子任务通过，第二个子任务WA，第三个子任务超时。请问还有没有进一步改进的方法呢？或者题解什么的?

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int N = 1000010;
int h[N], e[N], idx, ne[N];
int n, a[N], k[N];
int d[N];
bool st[N];
typedef pair<int, int> PII;

void add(int a, int b)
{
    if(idx>=N)return;
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver])
            continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            if (d[e[i]] > distance + 1)
            {
                d[e[i]] = distance + 1;
                heap.push({d[e[i]], e[i]});
            }
        }
    }
    if (d[n] == 0x3f3f3f3f)
        return -1;
    return d[n];
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &k[i]);

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k[i] && i + j <= n; j++)
        {
            add(i, i + j - a[i + j]);
        }
    }
    printf("%d\n", dijkstra());
}

Answer 1

让【道友老李】来帮你解答，本回答参考gpt编写，并整理提供，如果还有疑问可以点击头像关注私信或评论。

如果答案让您满意，请采纳、关注，非常感谢！

在你的代码中有一个地方可能导致runtime error，就是在 `d[e[j]] = min(d[e[j]], d[t] + 1);` 这一行中可能会访问到数组越界的位置。这是因为你在add函数中并没有限制e数组的大小，所以可能会导致访问到不合法的位置。 你可以尝试在代码中增加一个检查条件，限制e数组的大小不超过数组的最大值，例如在add函数中加入判断条件：

void add(int a, int b){
    if (idx >= N) return;
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

另外，你在main函数中输入n时未考虑n的值可能超出数组范围的情况，建议增加检查条件。 最后，关于更好的做法，除了Dijkstra算法外，你也可以考虑使用BFS或者SPFA算法来做最短路径问题。 希望对你有所帮助，如果还有其他问题或疑问，请随时提出。