用了三年的板子竟然T了

P4779 【模板】单源最短路径(标准版)

一架飞机 @ 2022-10-17 20:23:32

for(int i=1;i<=M-5;i++)dis[i]=1e10;
    dis[s]=0;q.push(mp(0,s));
    while(q.size()){
        int x=q.top().second;q.pop();
        //A
        for(int i=He[x];i;i=Nx[i]){
            int y=To[i],z=w[i];
            if(dis[y]>dis[x]+z){
                dis[y]=dis[x]+z;
                q.push(mp(-dis[y],y));
            }
        }
    }

在A处加上 if(b[x])continue;b[x]=1;就对了

按理说应该优化不了多少的吧?


by 一架飞机 @ 2022-10-19 20:36:23

@樱雪喵

我也是

但是这道题我不用vis要T


上一页 |