洛谷 P6145 [USACO20FEB] Timeline G

本文主要是介绍洛谷 P6145 [USACO20FEB] Timeline G，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[USACO20FEB] Timeline G

题目描述

Bessie 在过去的 $M$ 天内参加了 $N$ 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。

对于第 $i$ 次挤奶，Bessie 记得它不早于第 $S_i$ 天进行。另外，她还有 $C$ 条记忆，每条记忆形如一个三元组 $(a,b,x)$，含义是第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。

现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。

保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得：

• 第 $i$ 次挤奶不早于第 $S_i$ 天进行，且不晚于第 $M$ 天进行；
• 所有的记忆都得到满足；

输入格式

第一行三个整数 $N,M,C$。保证 $1\le N,C\le 10^5$，$2\le M\le 10^9$。

接下来一行包含 $N$ 个整数 $S_1,S_2,\dots ,S_n$，保证 $\forall 1\le i\le n$，都满足 $1\le S_i\le M$。

下面 $C$ 行每行三个整数 $a,b,x$，描述一条记忆。保证 $a\ne b$，且 $1\le x\le M$。

输出格式

输出 $N$ 行，每行一个整数，第 $i$ 行的数表示第 $i$ 次挤奶的最早日期。

样例 #1

样例输入 #1

4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4

样例输出 #1

1
6
3
8

提示

• 测试点 $2\sim 4$ 满足 $N,C\le 10^3$。
• 测试点 $5\sim 10$ 没有特殊限制。

#include<bits/stdc++.h>
using namespace std;
struct aty {int v,w;
};
vector<aty> E[100010];
queue<int> q;
int n,m,dis[100010],u,v,w,fw[100010],op,c,s[100010];
bool vis[100010];
int main() {scanf("%d%d%d",&n,&m,&c);for(int i=1; i<=n; i++) {scanf("%d",&s[i]);E[0].push_back({i,s[i]});}for(int i=1; i<=c; i++) {scanf("%d%d%d",&u,&v,&w);E[u].push_back({v,w});}for(int i=1; i<=n; i++) {dis[i]=-INT_MAX;}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>dis[E[u][i].v]) {dis[E[u][i].v]=dis[u]+E[u][i].w;/*	fw[E[u][i].v]++;if(fw[E[u][i].v]>n+1) {printf("No");return 0;}*/q.push(E[u][i].v);vis[E[u][i].v]=1;}}}for(int i=1;i<=n;i++){printf("%d\n",dis[i]); }return 0;
}

这篇关于洛谷 P6145 [USACO20FEB] Timeline G的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---