用最短路模型解决问题

例题 #1 [USACO04DEC] Cleaning Shifts S

一天有 \(T(1\le T\le 10^6)\) 个时段。约翰正打算安排他的 \(N(1\le N\le 2.5\times 10^4)\) 只奶牛来值班，打扫打扫牛棚卫生。每只奶牛都有自己的空闲时间段 $ S_i,E_i$，只能把空闲的奶牛安排出来值班。而且，每个时间段必需有奶牛在值班。

那么，最少需要动用多少奶牛参与值班呢？如果没有办法安排出合理的方案，就输出 \(-1\)。

\(1\le T\le 10^6\)，\(N\le 2.5\times 10^4\)，\(1\le S_i\le E_i\le T\)。

\(\text{Update On 2023/08/08}\)：添加了一组hack数据，详情见这里。叉掉了时间复杂度为 \(\mathcal O(nt)\) 的错解。

---

我们考虑对于每个区间[a,b]从a-1→b连一条v=1的边。然后为了解决从区间内部插入的情况，对于每个i，建边i→i-1,v=0。跑最短路即可。

const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

bool FLA;

struct node{
    itn v,w;
};
vector<node> e[N];
int d[N];
int n,t;
priority_queue<pii> pq;
int vis[N];

bool FLB;
void djstr(int s){
    for(itn i=0;i<=t;i++){
        d[i]=INF;
    }
    d[s]=0;
    pq.push(mp(d[s],s));
    while(pq.size()){
        int x=pq.top().ps;
        pq.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(auto v:e[x]){
            if(!vis[v.v]&&d[v.v]>d[x]+v.w){
                d[v.v]=d[x]+v.w;
                pq.push(mp(-d[v.v],v.v));
            }
        }
    }
}


void add(int a,itn b,int c){
    e[a].pb({b,c});
//  e[b].pb({a,c});
}
void solve(){
    cerr<<((&FLB)-(&FLA))/1024.0/1024.0<<" Mib"<<endl;

    n=rd;
    t=rd;
    for(itn i=1;i<=n;i++){
        int a=rd,b=rd;
        add(a-1,b,1);
    }
    for(int i=1;i<=t;i++){
        add(i,i-1,0);
    }

    djstr(0);

    if(d[t]==INF)cout<<-1<<endl;
    else cout<<d[t]<<endl;
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".in","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}