用了三年的板子竟然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 char_phi @ 2022-10-17 20:46:07

@樱雪喵 呃呃，如果不想 \text{T} 的话好像要开

by 樱雪喵 @ 2022-10-17 20:50:29

@char_phi

可是我印象中我这么多年 dij 从来没写过 vis 数组啊，怎么回事呢/qd

https://www.luogu.com.cn/record/36271731

by 樱雪喵 @ 2022-10-17 20:52:28

离大谱了/qd

by hj23308 @ 2022-10-17 20:52:45

@char_phi 呃呃 好像这个叫堆优化的 \texttt{Bellman-Ford}（？

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

@hj23308 草 我太蒻了所以当时没有学 \text{Bellman-Ford} 直接去学 \text{spfa} 了

涨芝士了qwq

by yizhiming @ 2022-10-17 20:57:24

在A出加上vis就是dij，不加貌似是楼上说的堆优Bellman-ford

by yizhiming @ 2022-10-17 20:59:35

至于堆优dij记不记vis，不同人写法不同，只要能保证每个点只会遍历其他点一次即可

by char_phi @ 2022-10-17 21:00:43

@樱雪喵 不清楚（（

但是神奇的是我的代码跑了154ms，您跑了一秒，可能加上比较好...

by char_phi @ 2022-10-17 21:01:41

学的版本不一样可能（

by char_phi @ 2022-10-17 21:02:57

@hj23308 我shab了，没看清 堆优化