P7480 Reboot from Blue - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

建图，跑最短路。

直接建图太大，其中很多路都是无用的。考虑优化，用数据结构找到一点前后第一个比该点油价低的即可。我用线段树来找这两个位置。

需要注意：

• dis[]值的初始化，0x3f3f3f3f不行（
• 边数要开大点，大概是$3\times N$条边
• 注意判断终点是否为加油站（（

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 21; // 注意：N要开大点
#define int long long
struct no {
    int c,x;
    bool operator<(const no& rhs) const {
        return x < rhs.x;
    }
}a[N];

// 基础线段树 - 最值
struct tree {
    int l, r, mi;
}tr[N << 2];
int inline ls(int x) {return x << 1; }
int inline rs(int x) {return x << 1 | 1; }
void pushup(int u) {
    tr[u].mi = min(tr[ls(u)].mi, tr[rs(u)].mi);
}
void build(int u, int l, int r) {
    if(l == r) tr[u] = {l, r, a[l].c};
    else {
        tr[u] = {l, r, (int)3e18};
        int mid = l + r >> 1;
        build(ls(u), l, mid);
        build(rs(u), mid + 1, r);
        pushup(u);
    }
}

// 查找左边第一个小于val的位置
int qryl(int u, int l, int r, int val) {
    if(tr[u].l == tr[u].r) {
        return tr[u].mi < val ? tr[u].l : -1;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(tr[u].l >= l && tr[u].r <= r) {
        // 先搜索右边的，保证最近
        if(tr[rs(u)].mi < val) return qryl(rs(u), l, r, val);
        // 再搜索左边的
        if(tr[ls(u)].mi < val) return qryl(ls(u), l, r, val);
        
        // 都没有找到，返回-1.左边不会有满足条件的了
        return -1;
    }

    // 这两段是是找区间(ql, qr)，保证 (ql, qr) 和(l, r) 有交集的
    if(r <= mid) return qryl(ls(u), l, r, val);
    if(l > mid) return qryl(rs(u), l, r, val);

    // 有交集的情况下，先搜索右边的，保证最近
    int res = qryl(rs(u), l, r, val);
    // 不为-1，说明找到了，直接返回
    if(res != -1) return res;
    // 没找到，再搜索左边的
    res = qryl(ls(u), l, r, val);
    return res;
}

// 查找右边第一个小于val的位置
    // 同上
int qryr(int u, int l, int r, int val) {
    if(tr[u].l == tr[u].r) {
        return tr[u].mi < val ? tr[u].l : -1;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(tr[u].l >= l && tr[u].r <= r) {
        if(tr[ls(u)].mi < val) return qryr(ls(u), l, r, val);
        if(tr[rs(u)].mi < val) return qryr(rs(u), l, r, val);
        return -1;
    }
    if(mid < l) return qryr(rs(u), l, r, val);
    if(mid >= r) return qryr(ls(u), l, r, val);
    int res = qryr(ls(u), l, r, val);
    if(res != -1) return res;
    res = qryr(rs(u), l, r, val);
    return res;
}

// dijstra堆优化模板
    // 这里N要开大点，因为：前后建边、与终点建边
int e[N],h[N], ne[N], w[N], idx, dis[N], vis[N];
void add(int u, int v, int val) {
    e[idx] = v, w[idx] = val, ne[idx] = h[u], h[u] = idx++;
}
signed main()
{
    ios::sync_with_stdio(0);
    int n, st, ed; cin>>n>>st>>ed;
    bool fg = true; // 终点不是加油站
    for(int i = 1; i <= n; ++i) {
        cin>>a[i].c>>a[i].x;
        if(a[i].x == ed) fg = false;
    }
    // 终点不是加油站，加一个虚拟加油站
    if(fg) {
        a[++n] = {-1, ed};
    }
    // 按照坐标x排序
    sort(a + 1, a + n + 1);

    // 建立线段树
    build(1, 1, n);

    // 建立图
    memset(h, -1, sizeof(h));
    // memset(dis, 0x3f, sizeof(dis));
    for(int i = 0; i <= n; ++i) dis[i] = 1e18;
    int dijst = -1, dijed = -1; // 终点有一个测试里可能有多个，要找到最优的作为终点
    for(int i = 1; i <= n; ++i) {
        if(a[i].x == st) dijst = i;
        if(a[i].x == ed) dijed = i;

        int lv = qryl(1, 1, i, a[i].c);
        if(lv != -1) {
            add(i, lv, a[i].c * abs(a[i].x - a[lv].x));
        }
        int rv = qryr(1, i, n, a[i].c);
        if(rv != -1) {
            add(i, rv, a[i].c * abs(a[i].x - a[rv].x));
        }
    }

    // 终点不是加油站，加边
    for(int i = 1; i <= n; ++i) {
        if(i == dijed) continue;
        add(i, dijed, a[i].c * abs(a[i].x - a[dijed].x));
    }

    // 跑dijstra
    dis[dijst] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    q.push({0, dijst});
    while(q.size()) {
        auto tmp = q.top(); q.pop();
        int u = tmp.second, d = tmp.first;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = h[u]; ~i; i = ne[i]) {
            int y = e[i];
            if(dis[y] > dis[u] + w[i]) {
                dis[y] = dis[u] + w[i];
                q.push({dis[y], y});
            }
        }
    }

    cout<<dis[dijed]<<'\n';
}