dijkstra (好像有问题)
单源最短路,原理比较简单,就是贪心。每次选取最近的边(没选过),用它去更新其他的。传统做法是每次扫一遍寻找最近的遍,其实可以用堆优化。
void dijkstra(int s) {
q.push(JCY{s, 0});
for (int i = 1; i <= n + n; i++) {
num[i] = 0x3f3f3f3f; //有因为最短路
}
num[s] = 0;//自己到自己是0
while (q.size()) {
JCY p = q.top();
q.pop();
if (vis[p.id]) { //选过了
continue; // 不要
}
vis[p.id] = 1; // 标为选过
for (int j = h[p.id]; j; j = ne[j]) {
int v = e[j];
if (num[v] > num[p.id] + w[j]) { //如果能更新
num[v] = num[p.id] + w[j];
q.push(JCY{v, num[v]}); //可以对其他人有贡献
}
}
}
}
因为每个点都会进队列 \(O(n)\),然后每次更新 \(O(m)\),堆 \(O(log)\),总共 \(O((n + m)log n)\)
spfa
类似于广搜,选择一个点,然后进行更新
void spfa() {
for (int i = 1; i <= n; i++) {
num[i] = 0x3f3f3f3f; //不说
}
num[s] = 0;
vis[s] = 1; //是否在队列里
q.push(s);
while (q.size()) {
int u = q.front(), v;
q.pop();
vis[u] = 0;
for (int i = h[u]; i; i = ne[i]) {
v = e[i];
if (num[v] > num[u] + w[i]) { //松弛
num[v] = num[u] + w[i];
if (!vis[v]) { //不在队列
q.push(v);//进队
vis[v] = 1;
}
}
}
}
}
还一个晚点写(鸽了好久,不想管了呢)
标签:int,短路,JCY,更新,num,push From: https://www.cnblogs.com/jiangyuchen12/p/17685913.html