关于第一问的搜索起点
查看原帖
关于第一问的搜索起点
528114
jjsnam楼主2022/3/19 22:09

为什么是从1开始? 这是AC记录 核心代码如下

void bfs(int u){
    q[0]=u;
    sum++;
    vis[u]=true;
    while (hh<=tt){
        u=q[hh++];
        for (int i=p[u];~i;i=g[i].next){
            int v=g[i].v,w=g[i].w;
            if (h[v]<=h[u]){
                if (!vis[v]){
                    vis[v]=true;
                    sum++;
                    q[++tt]=v;
                }
                e[++cnt]=(Edge){u,v,w};
            }
        }
    }
}

bfs(1);

题目中并没有说明高度单调递减,也没有说明起点是1,而且即使单调递减,看下面这个数据⬇️

5 6 
5 4 3 2 1
2 3 1
3 4 1
4 5 4
1 4 5
3 5 114514
2 4 4

数据 程序跑出来的是(以1为起点)(题解的代码也是这个结果)

3 9

但显然答案应该是(以2为起点)

4 6

不知道是题目描述的问题还是我没有完全理解…… 或者是数据太弱

求大佬解释!

2022/3/19 22:09
加载中...