Dij板子求助

P1342 请柬

或许是因为Min不能每次i循环都改成最大值...
by voruala @ 2021-11-16 11:29:39


@[nyaku](/user/170618) 那改成什么? 没明白qwq
by Australia @ 2021-11-16 11:40:47


你如果会堆优化可以写堆优化,如果不会就写 ```c++ Min=0x3f3f3f3f; for(j=1;j<=n;j++) if(d[j]<Min) Min=d[j],wyx=j; ``` 但是可能会t。而且你需要写个`vis`数组,确保每个`d[j]`只被访问一次
by voruala @ 2021-11-16 12:07:24


```c++ if(d[edge[j].to]<Min) { Min=d[edge[j].to]; wyx=edge[j].to; } ``` 和这个$if$应该放在外面那层$if$的下面而非里面,因为新更新的$dis$不一定是最小的(大概 另外,如果不写堆优化的话,$1e6$的数据量可能过不了模板题,建议看博客学习一下堆优化((
by AobaMocaa @ 2021-11-16 12:19:24


@[AobaMocaa](/user/227177) @[nyaku](/user/170618) 谢谢两位大佬,想明白了
by Australia @ 2021-11-16 15:57:38


|