正确的 Dijkstra 到底需不需要 vis 数组啊qwq
OI Wiki 给出的模板没有 vis 数组
vector<vector<LL>> Ps; // 图的邻接矩阵
vector<LL> dist; // min_len 的运行结果存储位置
// i: 源点在点集中的下标
void min_len(size_t i) {
using Pair = pair<LL, size_t>; // pair 的排序是先第一分量后第二分量,
// 通过这个可以调整它在堆中的位置
// 初始化 dist
for (auto &k : dist) k = LLONG_MAX;
dist[i] = 0;
// 初始化小根堆
priority_queue<Pair, vector<Pair>, greater<Pair>> Q; // 小根堆
Q.push(Pair(0, i));
while (!Q.empty()) {
auto k = Q.top().second;
Q.pop();
for (size_t i = 0; i < Ps[k].size(); i++) {
// 如果 k 和 i 有边连(这里设置 Ps[k][i] == 0 时无边连接)
if (Ps[k][i] && dist[k] + Ps[k][i] < dist[i]) {
// 松弛操作
dist[i] = dist[k] + Ps[k][i];
Q.push(Pair(dist[i], i));
}
}
}
}
但蓝书的模板上使用了 vis 数组,感觉好奇怪……