用了三年的板子竟然T了

一架飞机 @ 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));
            }
        }
    }

by LHQing @ 2022-10-17 20:25:53

这怎么优化不了多少

你不加这个复杂度是指数级别的好吧

by char_phi @ 2022-10-17 20:26:34

您是不是没仔细学 \text{dijkstra}。。。

by Super_Supper @ 2022-10-17 20:29:11

@char_phi 这不是 SPFA 吗（？

by char_phi @ 2022-10-17 20:32:28

@sb_yyds 这咋可能是 \text{spfa}（（

by char_phi @ 2022-10-17 20:33:08

当然如果您用玄学优化 \text{spfa} 那当我没说（

by shyr @ 2022-10-17 20:33:52

@sb_yyds 众所周知普通队列取队头用 q.top()

by hj23308 @ 2022-10-17 20:34:49

应该算是优化的 \texttt{Bellman-Ford} 吧

by Super_Supper @ 2022-10-17 20:39:17

wssb

by 樱雪喵 @ 2022-10-17 20:41:33

是我傻了吗，dij 为啥要开 vis 数组/qd

by char_phi @ 2022-10-17 20:42:16

@hj23308 草