Solution-P1668

wangzikang · 2023-07-10 10:01:24 · 题解

来个最短路题解。

我们建立一条从 t+1 到 1 的长度为0的链，以样例为例，如图：

对于每一个奶牛，我们新建一个点，然后从 s_i 连到这个点，再从这个点连到 e_i+1，使这两条边的总边权为1，如图：

显然，1-t+1 的最短路就是答案。

我们可以感性理解：走到时间轴上的某个点时代表前面的时刻都有人值班，所以我们可以反着走：我们从 s_i 到 e_i+1 花一个边权的过程，就是让一个奶牛从 s_i 值班到 e_i，由于走到时间轴上的某个点时代表前面的时刻都有人值班，所以我们应该直接走到 e_i+1。

注意常数因子带来的时间复杂度影响。

code：

#include<bits/stdc++.h>
const int MAXN=2e6+10,MAXM=5e6+10;
using namespace std;
int s,t,k;
struct node{
    int nxt,to,dis;
}g[MAXM<<1];
int n,m,head[MAXN],cnt,dis[MAXN],vis[MAXN];
void add(int u,int v,int w){
    g[++cnt].nxt=head[u],head[u]=cnt,g[cnt].to=v,g[cnt].dis=w;
}
priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > >q;
void dij(int s){//乐 
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=g[i].nxt){
            int v=g[i].to;
            if(!vis[v]&&(dis[v]>dis[u]+g[i].dis)){
                dis[v]=min(dis[v],dis[u]+g[i].dis);
                q.push(make_pair(dis[v],v));
                vis[v]=1;
            }
            dis[v]=min(dis[v],dis[u]+g[i].dis);
        }
    }
}
signed main(){

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int cnt=1;
    for(int i=1;i<m;++i){
        add(i+1,i,0);
    }
    for(int i=1;i<=n;++i){
        int l,r;
        cin>>l>>r;
        add(l,m+(++cnt),0);
        add(m+cnt,r+1,1);
    }
    dij(1);
    cout<<(dis[m+1]==0x3f3f3f3f?-1:dis[m+1]);
    return 0;
}