线段树优化的Dijkstra板子

板子

我测得的是这个东西在不开\(O2\)的情况下比\(pair + priority_queue\)快了将近\(1/3\)

#include<bits/stdc++.h>
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r


using namespace std;

const int N1 = 1e5 + 10, N2 = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int head[N1], to[N2], nex[N2], value[N2], cnt;

int dis[N1];

int n, m, s;

inline int read(){
	int x = 0,f=1;char ch = getchar();
	while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
	while(ch<=‘9‘&&ch>=‘0‘){x=x*10+ch-‘0‘;ch=getchar();}
	return x*f;
}

struct point {
    int id, dis;
    point(int a = 0, int b = 0) : id(a), dis(b) {}
}a[N1 << 2];

point minp(point a, point b) {
    if(a.dis < b.dis)   return a;
    return b;
}

void build_tree(int rt, int l, int r) {
    if(l == r) {
        a[rt].id = l;
        a[rt].dis = INF;
        return ;
    }
    build_tree(lson);
    build_tree(rson);
    a[rt].dis = INF;
    a[rt].id = a[rt << 1].id;
}

void update_tree(int rt, int l, int r, int dis, int x) {
    if(l == r) {
        a[rt].dis = x;
        return ;
    }
    if(dis <= mid)  update_tree(lson, dis, x);
    else            update_tree(rson, dis, x);
    a[rt] = minp(a[rt << 1], a[rt << 1 | 1]);
}

void add(int x, int y, int w) {
    to[cnt] = y;
    nex[cnt] = head[x];
    value[cnt] = w;
    head[x] = cnt++;
}

void print_tree(int rt, int l, int r) {
    printf("%d %d\n", rt, a[rt].id);
    if(l == r) {
        // printf("%d %d\n", a[rt].id, a[rt].dis);
        return ;
    }
    print_tree(lson);
    print_tree(rson);
}

void Dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    // print_tree(1, 1, n);
    update_tree(1, 1, n, 1, 0);
    // puts("");
    // print_tree(1, 1, n);
    for(int cas = 1; cas < n; cas++) {
        // cout << 1 << endl;
        point temp = a[1];
        // printf("%d %d\n", temp.id, temp.dis);
        update_tree(1, 1, n, temp.id, INF);
        for(int i = head[temp.id]; ~i; i = nex[i]) {
            if(dis[to[i]] > dis[temp.id] + value[i]) {
                // cout << 1 << endl;
                dis[to[i]] = dis[temp.id] + value[i];
                update_tree(1, 1, n, to[i], dis[to[i]]);
            }
        }
    }
    for(int i = 1; i <= n; i++)
        printf("%d%c", dis[i], i == n ? ‘\n‘ : ‘ ‘);
}

int main() {
    // freopen("in.txt", "r", stdin);
    int x, y, w;
    memset(head, -1, sizeof head);
    n = read(), m = read(), s = read();
    build_tree(1, 1, n);
    for(int i = 0; i < m; i++) {
        x = read(), y = read(), w = read();
        // scanf("%d %d %d", &x, &y, &w);
        add(x, y, w);
    }
    Dijkstra();
    return 0;
}

线段树优化的Dijkstra板子

原文：https://www.cnblogs.com/lifehappy/p/12920476.html