洛谷 P1250 种树

本文介绍: 一条街的一边有几座房子，因为环保原因居民想要在路边种些树。

种树

题目背景

一条街的一边有几座房子，因为环保原因居民想要在路边种些树。

题目 描述

路边的地区被分割成块，并被编号成

…

1, 2, ldots,n

$1, 2, \dots, n$ 。每个部分为一个单位尺寸大小并最多可种一棵树。

每个居民都想在门前种些树，并指定了三个号码

$b$ ，

$e$ ，

$t$ 。这三个数表示该居民想在地区

$b$ 和

$e$ 之间（包括

$b$ 和

$e$ ）种至少

$t$ 棵树。

居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

输入 格式

输入的第一行是一个整数，代表区域的个数

$n$ 。

输入的第二行是一个整数，代表房子个数

$h$ 。

第

$3$ 到第

(

)

(h + 2)

$(h + 2)$ 行，每行三个整数，第

(

)

(i + 2)

$(i + 2)$ 行的整数依次为

b_i, e_i, t_i

$b_{i}, e_{i}, t_{i}$ ，代表第

$i$ 个居民想在

b_i

$b_{i}$ 和

e_i

$e_{i}$ 之间种至少

t_i

$t_{i}$ 棵树。

输出 格式

输出一行一个整数，代表最少的树木个数。

样例 #1

样例输入 #1

样例 输出 #1

提示

数据规模与约定

对于

100

100%

$100%$ 的数据，保证：

$10^4 1≤n≤3×104， 1 ≤ h ≤ 5 × 1 0 3 1 leq h leq 5 times 10^3 1≤h≤5×103。$
$b_i leq e_i leq n 1≤bi≤ei≤n， 1 ≤ t i ≤ e i − b i + 1 1 leq t_i leq e_i – b_i + 1 1≤ti≤ei−bi+1。$

#include<bits/stdc++.h&gt;
using namespace std;
struct aty {
	int v,w;
};
vector<aty&gt; E[100010];
queue<int&gt; q;
int n,m,dis[100010],u,v,w,fw[100010],op,c,s[100010];
bool vis[100010];
int main() {
	scanf("%d%d",&amp;n,&amp;m);
	for(int i=1; i<=m; i++) {
		scanf("%d%d%d",&amp;u,&amp;v,&amp;w);
		E[u-1].push_back({v,w});
	}
	for(int i=1; i<=n; i++) {
		dis[i]=-INT_MAX;
		E[i].push_back({i-1,-1});
		E[i-1].push_back({i,0});

	}
	dis[0]=0;
//	fw[0]=1;
	q.push(0);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=0; i<E[u].size(); i++) {
			if(dis[u]+E[u][i].w&gt;dis[E[u][i].v]) {
				dis[E[u][i].v]=dis[u]+E[u][i].w;
				if(!vis[E[u][i].v]) {
					q.push(E[u][i].v);
					vis[E[u][i].v]=1;
				}

			}
		}
	}
	printf("%d",dis[n]);
	return 0;
}