最短路之清理牛棚

题目

传送们P4644 [USACO05DEC]Cleaning Shifts S

思路

*这道题的思路很清奇，很难想到，我们把时间的起点和终点存为求最短路的起点和终点，把每个奶牛的起始点和终止点存为节点，将奶牛需要的工资作为距离，并且从终点枚举一遍到起点，两两整时间相连，且距离为0，就可以直接跑spfa了，是不是很神奇，这也是把这道题归为图论最短路的原因
*思路没有问题了，主要是一些小细节，比如时间段，时间段！！！

下面是代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct edge{
    int dis,to,next;
}e[maxn];
int n,m,E;
int head[maxn],cnt;
int add(int from,int to,int dis){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].dis=dis;
    head[from]=cnt;
}
int vis[maxn],dis[maxn];
queue<int>q;
void spfa(){
    for(int i=m;i<=E;i++){
        dis[i]=0x7f7f7f7f;
        vis[i]=0;
    }
    q.push(m);
    vis[m]=1;
    dis[m]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].dis){
                dis[v]=dis[u]+e[i].dis;
                if(vis[v]==0){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }

    }

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

int main(){
    n=read();m=read();E=read();
    E++;
    for(int i=1;i<=n;i++){
        int x,y,z;
        x=read(),y=read(),z=read();
        add(x,y+1,z);
    }
    for(int i=m;i<=E-1;i++){
        add(i,i-1,0);
    }
    spfa();
    if(dis[E]==0x7f7f7f7f){
        printf("-1");
        return 0;
    }
    else printf("%d",dis[E]);
    return 0;

}