如果是我指出来的那个问题的话不要2元，能不能给个关注
by hgckythgcfhk @ 2024-04-27 18:36:37
@[hgckythgcfhk](/user/692274) 二分的while里面是l<r (?
by _nothingGG @ 2024-04-27 19:11:19
@[Robots75](/user/1021365) @[hgckythgcfhk](/user/692274) 非常感谢二位！
首先我自己发现了一个错误，二分里面 `r = m - 1` 写成了 `r = m + 1`，不过根据我的测试（就是注掉的那两行）死循环是 Dij 的问题，第一个 `check()` 就卡了。
@[hgckythgcfhk](/user/692274) 码风上的问题受教了，非常感谢，不过大概不是那几个问题……这个题不用 `vector` 主要是因为判断每条边是否大于 $x$ 用 `vector` 稍微有点麻烦，我马上用 `vector` 写一遍试一下。
另外这是我已经 AC 的 Dijkstra 板子，无论我怎么对照都发现不了问题……
```cpp
#include <cstring>
#include <iostream>
#include <bitset>
#include <vector>
#include <queue>
struct Edge
{
int v, w;
friend bool operator>(Edge a, Edge b) { return a.w > b.w; }
};
int n, m, s;
int dis[100005];
std::bitset<100005> vis;
std::vector<Edge> edge[200005];
std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
void dijkstra()
{
memset(dis, 0x3f, 4 * (n + 1));
dis[s] = 0;
pq.push({s, 0});
while (!pq.empty())
{
int u = pq.top().v;
pq.pop();
if (vis[u])
continue;
vis[u] = true;
for (auto x : edge[u])
{
int v = x.v, w = x.w;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pq.push({v, dis[v]});
}
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int u, v, w;
std::cin >> u >> v >> w;
edge[u].push_back({v, w});
}
dijkstra();
for (int i = 1; i <= n; i++)
std::cout << dis[i] << " ";
std::cout << "\n";
return 0;
}
```
by lzy20091001 @ 2024-04-27 19:59:20
> 首先我自己发现了一个错误，二分里面 `r = m - 1` 写成了 `r = m + 1`，不过根据我的测试（就是注掉的那两行）死循环是 Dij 的问题，第一个 `check()` 就卡了。
好吧就当我在放屁，之前我的脑子不知出了什么问题，就这一个二分写错了
by lzy20091001 @ 2024-04-27 20:23:50
<https://www.luogu.com.cn/record/157280257> 现已 AC
by lzy20091001 @ 2024-04-27 20:24:34
@[hgckythgcfhk](/user/692274) 你不知道，链式前向星的好。我一起还专门发个帖子吐槽链式前向星（。现在都是基本不用vector了。
by Crab_Tang @ 2024-04-27 20:40:54
@[lzy20091001](/user/932039)
~~~ cpp
/*
ans=l=1,r=a;
while(r>=l)
{
m=(l+r)/2;
if(m*b>a)
r=m-1;
else
ans=m,l=m+1;
}
*/
~~~
提供一个二分
楼主二分可用多关注关注，这个二分有点离谱。r=m+1都能写出来的。。。。 @[lzy20091001](/user/932039)
by Crab_Tang @ 2024-04-27 20:43:03
@[lzy20091001](/user/932039) 你这个马蜂尤其是std的问题你每次都要写std::很烦的。。
by Crab_Tang @ 2024-04-27 20:43:47
@[lzy20091001](/user/932039) 这种memset的想要卡常就像那个红名大佬说的。你虽然想卡常但是卡不到。还有迪杰斯特拉的这个大根堆，默认是大根啊，所以你重载小于号的时候要反过来变成大于号，就像我发你的剪贴板的那样，2元不要了，关注一下可以
by Crab_Tang @ 2024-04-27 20:47:33
@[Robots75](/user/1021365) `r = m + 1` wssb
码风的话~~我是强迫症~~比较喜欢写
by lzy20091001 @ 2024-04-27 20:47:37