关于这题用dij求最长路的同学们
查看原帖
关于这题用dij求最长路的同学们
808950
iqwl楼主2023/9/21 16:53

把用来判断最长路是否已经确定的st数组删掉就好了,因为可能还会被更新成更优解。

void dij()
{
    queue<pii>q;//bool in[N];

    dist[id[s]]=sz[id[s]];
    q.push({sz[id[s]],id[s]});

    while(q.size())
    {
        int u=q.front().second;
        q.pop();

        //if(in[u])continue;
        //in[u]=true;

        for(auto v:g[u])
        {
            if(dist[v]<dist[u]+sz[v])
            {
                dist[v]=dist[u]+sz[v];
                q.push({dist[v],v});
            }
        }
    }
}
2023/9/21 16:53
加载中...