关于这道题的些许疑惑
查看原帖
关于这道题的些许疑惑
590609
jiangjiangQwQ楼主2024/7/19 13:00
void dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    q.push((node) { 1, 1, K, 0 });
    dis[1][1][K] = 0;
    while (q.size()) {
        node fr = q.top();
        q.pop();
        int ux = fr.x, uy = fr.y, uk = fr.k;
        if (vis[ux][uy][uk]) continue;
        vis[ux][uy][uk] = 1;
        if(map[ux][uy]&&uk!=K){
            if(dis[ux][uy][K]>dis[ux][uy][uk]+a){
                dis[ux][uy][K]=dis[ux][uy][uk]+a;
                q.push((node){ux,uy,K,dis[ux][uy][K]});
            }continue;
        }else{
            if(dis[ux][uy][K]>dis[ux][uy][uk]+a+c){
                dis[ux][uy][K]=dis[ux][uy][uk]+a+c;
                q.push((node){ux,uy,K,dis[ux][uy][K]});
            }
        }
        for(int i=0;i<4;i++){
            int nx=ux+dir[i][0],ny=uy+dir[i][1],w=(nx<ux||ny<uy)?b:0;
            if(!check(ux,uy)) continue;
            if(dis[nx][ny][uk-1]>dis[ux][uy][uk]+w&&uk-1>=0){
                dis[nx][ny][uk-1]=dis[ux][uy][uk]+w;
                q.push((node){nx,ny,uk-1,dis[nx][ny][uk-1]});
            }
        }
    }
}

这是我的 dijkstra 的部分,请问一下为什么其中这段代码要这么写?

if(map[ux][uy]&&uk!=K){//疑点1:这里为什么要判断uk!=K
            if(dis[ux][uy][K]>dis[ux][uy][uk]+a){
                dis[ux][uy][K]=dis[ux][uy][uk]+a;
                q.push((node){ux,uy,K,dis[ux][uy][K]});
            }continue;//疑点2:为什么直接continue
        }else{
            if(dis[ux][uy][K]>dis[ux][uy][uk]+a+c){
                dis[ux][uy][K]=dis[ux][uy][uk]+a+c;
                q.push((node){ux,uy,K,dis[ux][uy][K]});
            }
        }
2024/7/19 13:00
加载中...