正題

luogu 4644

---

題目大意

給你一段時間，有n頭奶牛，第i頭可以花費$s_i$的代價清理$l_i$到$r_i$，問你清理完所有時間段的最小代價

---

解題思路

所有點需求都為1的線性規劃，直接代入最短路就可以了

---

code

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100010 #define mp make_pair #define fs first #define sn second using namespace std; ll n,l,r,x,y,z,tot,p[N],b[N],h[N]; priority_queue<pair<ll,ll> >d; struct rec {ll to,nx,l; }e[N<<2]; void add(ll x,ll y,ll z) {e[++tot].to=y;e[tot].l=z;e[tot].nx=h[x];h[x]=tot;return; } bool dij() {memset(b,127/3,sizeof(b));b[l] = 0;d.push(mp(0,l));while(!d.empty()){ll u=d.top().sn;d.pop();if(p[u])continue;p[u]=1;for(int i=h[u];i;i=e[i].nx){ll v=e[i].to;if(b[u]+e[i].l<b[v]){b[v]=b[u]+e[i].l;d.push(mp(-b[v],v));}}}return p[r+1]; } int main() {scanf("%lld%lld%lld",&n,&l,&r);for(int i=l;i<r;++i)add(i+1,i,0);for(int i=1;i<=n;++i){scanf("%lld%lld%lld",&x,&y,&z);add(x,y+1,z);}if(dij())printf("%lld",b[r+1]);else puts("-1");return 0; }

總結

以上是生活随笔為你收集整理的【图论】清理牛棚/Cleaning Shifts S（luogu 4644）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。