“进阶”
如何用线段树查询某个区间 $[l,r]$ 中是 $x$ 的倍数的数的个数？
在线等
急

$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

Bellman-Ford 算法：
有点S*的算法

1. 循环 $n$ 次。
2. 每层循环循环每条边，使用三角不等式进行松弛操作。
3. 可以处理负权边，判断负环。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4 + 10;
int n, m, k;
int dist[N], back[N];
struct Edge {
    int a, b, c;
} edge[M];

int bellman_ford() {
    dist[1] = 0;
    for (int i = 1; i <= k; i++) {
        memcpy(back, dist, sizeof dist);
        for (int j = 1; j <= m; j++) {
            int a = edge[j].a, b = edge[j].b, w = edge[j].c;
            dist[b] = min(dist[b], back[a] + w);
        }
    }
    if (dist[n] >= 0x3f3f3f3f / 2) return -0x3f3f3f3f;
    return dist[n];
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        edge[i] = {u, v, w};
    }
    memset(dist, 0x3f3f3f3f, sizeof dist);
    int ans = bellman_ford();
    if (ans == -0x3f3f3f3f) puts("impossible");
    else printf("%d", ans);
    return 0;
}

$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

Bellman-Ford 算法：
有点S*的算法

1. 循环 $n$ 次。
2. 每层循环循环每条边，使用三角不等式进行松弛操作。
3. 可以处理负权边，判断负环。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4 + 10;
int n, m, k;
int dist[N], back[N];
struct Edge {
    int a, b, c;
} edge[M];

int bellman_ford() {
    dist[1] = 0;
    for (int i = 1; i <= k; i++) {
        memcpy(back, dist, sizeof dist);
        for (int j = 1; j <= m; j++) {
            int a = edge[j].a, b = edge[j].b, w = edge[j].c;
            dist[b] = min(dist[b], back[a] + w);
        }
    }
    if (dist[n] >= 0x3f3f3f3f / 2) return -0x3f3f3f3f;
    return dist[n];
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        edge[i] = {u, v, w};
    }
    memset(dist, 0x3f3f3f3f, sizeof dist);
    int ans = bellman_ford();
    if (ans == -0x3f3f3f3f) puts("impossible");
    else printf("%d", ans);
    return 0;
}

$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

对AcWing 849. Dijkstra求最短路 I进行堆优化。

堆优化手写堆参照AcWing 839. 模拟堆
当然可以用优先队列，但是可惜优先队列不能控制元素个数（
所以优先队列中可能会出现 $m$ 个元素。
但是可以 AC 了。

由于这题是稀疏图，因此要采用链式前向星进行存储。
时间复杂度 $O(m~\log~n)$。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
bool st[N];
int n, m, tot;
priority_queue< pair<int, int> > q;
void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
    memset(d, 0x3f3f3f3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    q.push({0, 1});
    while (q.size()) {
        int x = q.top().second;
        q.pop();
        if (st[x]) continue;
        st[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i =1 ; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dijkstra();
    if (d[n] != 0x3f3f3f3f) cout<<d[n];
    else puts("-1");
}

$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

对AcWing 849. Dijkstra求最短路 I进行堆优化。

堆优化手写堆参照AcWing 839. 模拟堆
当然可以用优先队列，但是可惜优先队列不能控制元素个数（
所以优先队列中可能会出现 $m$ 个元素。
但是可以 AC 了。

由于这题是稀疏图，因此要采用链式前向星进行存储。
时间复杂度 $O(m~\log~n)$。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
bool st[N];
int n, m, tot;
priority_queue< pair<int, int> > q;
void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
    memset(d, 0x3f3f3f3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    q.push({0, 1});
    while (q.size()) {
        int x = q.top().second;
        q.pop();
        if (st[x]) continue;
        st[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i =1 ; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dijkstra();
    if (d[n] != 0x3f3f3f3f) cout<<d[n];
    else puts("-1");
}