[lnsyoj1469/luoguP4644] Cleaning Shifts

题意

原题链接
给定 \(n\) 个区间 \([a_i,b_i]\)，第 \(i\) 个区间拥有权值 \(S_i\)，求使用这些区间将区间 \([M,E]\)（包含所有 \(n\) 个区间）完全覆盖（两端点不需要重合）所需区间的权值最小值。

sol

一道板子题，本来是数据结构优化 DP，但是被最短路薄纱了。
考虑将每一个时间点视作一个节点，这样问题就转化为了从起始点到终止点的路径问题。将每个区间转化为一条 \(a_i \to b_i + 1\)，权值为 \(S_i\) 的边，注意由于端点不需要重合，因此需要将 \(n\) 个点拆成 \(n+1\) 个点，因此终点要 \(+1\)。
考虑相交的区间，可以再连接 \(i+1 \to i\)，权值为 \(0\) 的边。这样只需要求出 \(M\) 到 \(E + 1\) 的最短路就可以解决问题了
注意会爆 int

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

#define x first 
#define y second 

using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;

const int N = 100005, M = 200005;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int h[N], e[M], w[M], ne[M], idx;
int n, start, ed;
LL dist[N];
bool st[N];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    dist[start] = 0;
    heap.push({0, start});

    while (!heap.empty()){
        PII t = heap.top();
        heap.pop();
        if (st[t.y]) continue;
        st[t.y] = true;

        for (int i = h[t.y]; ~i; i = ne[i]){
            int j = e[i];
            if (dist[j] > dist[t.y] + w[i]) {
                dist[j] = dist[t.y] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main(){
    memset(h, -1, sizeof h);

    scanf("%d%d%d", &n, &start, &ed);
    for (int i = start; i <= ed; i ++ ) add(i + 1, i, 0);

    while (n -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b + 1, c);
    }

    dijkstra();

    printf("%lld\n", dist[ed + 1] == INF ? -1 : dist[ed + 1]);
}