网站建设功能文案,南宁良庆网站建设,福州自助建站网站,网站开发工程师有证书考试吗种树
题目背景
一条街的一边有几座房子#xff0c;因为环保原因居民想要在路边种些树。
题目描述
路边的地区被分割成块#xff0c;并被编号成 1 , 2 , … , n 1, 2, \ldots,n 1,2,…,n。每个部分为一个单位尺寸大小并最多可种一棵树。
每个居民都想在门前种些树#…种树
题目背景
一条街的一边有几座房子因为环保原因居民想要在路边种些树。
题目描述
路边的地区被分割成块并被编号成 1 , 2 , … , n 1, 2, \ldots,n 1,2,…,n。每个部分为一个单位尺寸大小并最多可种一棵树。
每个居民都想在门前种些树并指定了三个号码 b b b e e e t t t。这三个数表示该居民想在地区 b b b 和 e e e 之间包括 b b b 和 e e e种至少 t t t 棵树。
居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
输入格式
输入的第一行是一个整数代表区域的个数 n n n。
输入的第二行是一个整数代表房子个数 h h h。
第 3 3 3 到第 ( h 2 ) (h 2) (h2) 行每行三个整数第 ( i 2 ) (i 2) (i2) 行的整数依次为 b i , e i , t i b_i, e_i, t_i bi,ei,ti代表第 i i i 个居民想在 b i b_i bi 和 e i e_i ei 之间种至少 t i t_i ti 棵树。
输出格式
输出一行一个整数代表最少的树木个数。
样例 #1
样例输入 #1
9
4
1 4 2
4 6 2
8 9 2
3 5 2样例输出 #1
5提示
数据规模与约定
对于 100 % 100\% 100% 的数据保证 1 ≤ n ≤ 3 × 1 0 4 1 \leq n \leq 3 \times 10^4 1≤n≤3×104 1 ≤ h ≤ 5 × 1 0 3 1 \leq h \leq 5 \times 10^3 1≤h≤5×103。 1 ≤ b i ≤ e i ≤ n 1 \leq 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−bi1。
#includebits/stdc.h
using namespace std;
struct aty {int v,w;
};
vectoraty E[100010];
queueint q;
int n,m,dis[100010],u,v,w,fw[100010],op,c,s[100010];
bool vis[100010];
int main() {scanf(%d%d,n,m);for(int i1; im; i) {scanf(%d%d%d,u,v,w);E[u-1].push_back({v,w});}for(int i1; in; 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 uq.front();q.pop();vis[u]false;for(int i0; iE[u].size(); i) {if(dis[u]E[u][i].wdis[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;
}
