题解 P4644 【[Usaco2005 Dec]Cleaning Shifts 清理牛棚】

· · 题解

如果没有权值 此题为一个简单的线段覆盖问题 但是现在我们有了权值 问题就变了 接下来是我的思路

那么我们一定是通过线段进行跳跃 也就是我们利用了线段离我们的目标更近了一步 比如__——（不止这两条线段）对于这种线段无重叠情况 我们很容易想到解法 也就是对线段之间连边 我们只需要考虑起点到终点最大值 

for(int i=1;i<=n;i++){
scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);add(node[i].a,node[i].b+1,node[i].c);}```
这样建边 对每一个线段点作为图中点 就可以解决问题

------------
对于重叠情况 我们可以发现需要往后走几步才会到达下一个线段首端而且这样是没有代价的 所以可以有

for(int i=m;i<=s;i++) { add(i,i-1,0);
}``` 到此 问题完美解决 下面是代码(spfa)


#include <bits/stdc++.h>
using namespace std;
struct p{
    int a,b,c;
}node[20010];
int cmp(p a,p b){
return a.a<b.a; 
}
int n,m,s,k;
struct z{
int v,next,w;   
}st[200010];
int head[200010],dis[200010],vis[200010];
int add(int a,int b,int c){
st[++k].v=b ;
st[k].w=c;
st[k].next=head[a];
head[a]=k;
}
int spfa()
{
    for(int i=m;i<=s+1;i++)
    dis[i]=1000000000;
queue<int> q;
q.push(m);
vis[m]=1;
dis[m]=0;
while(!q.empty()){
int v=q.front();
q.pop();
vis[v]=0;
for(int i=head[v];i;i=st[i].next){
int w=st[i].w,u=st[i].v;
if(dis[u]>dis[v]+w){
dis[u]=dis[v]+w;
if(!vis[u]){
vis[u]=1;
q.push(u);  
}   
}   
}   
}

}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);add(node[i].a,node[i].b+1,node[i].c);}
for(int i=m;i<=s;i++)
{
add(i,i-1,0);   
    }   
    spfa();
    printf("%d",dis[s+1]);
} ```