断网测试1-拓扑排序-Timeline G

洛谷P6145 第1题     Timeline G 查看测评数据信息

输入格式

输出格式

输入/输出例子1

输入：

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

输出：

1
6
3
8

样例解释

无

第b次挤奶在a几挤奶结束至少x天后结束，所以用拓扑

跟奖金很想，可以但是不用倒推了，正推即可（因为都是建图原因），注意longlong（可能不用开）

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;
struct node
{
	int v;
	long long w;
};
int n, m, c, s[N], u1, v1, d[N], b[N], cnt=0;
vector<node> a[N];
long long w1, te[N];
queue<int> q;
long long max2(long long a, long long b)
{
	if (a>b) return a;
	else return b;
}
long long min2(long long a, long long b)
{
	if (a<b) return a;
	else return b;
}
int main()
{
	scanf("%d%lld%d", &n, &m, &c);
	for (int i=1; i<=n; i++) scanf("%d", &s[i]);
	for (int i=1; i<=c; i++)
	{
		scanf("%d%d%lld", &u1, &v1, &w1);
		a[u1].push_back({v1, w1});
		d[v1]++;
	}
	
	for (int i=1; i<=n; i++)
		if (!d[i]) q.push(i);
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		b[++cnt]=u;
		
		for (int i=0; i<a[u].size(); i++)
		{
			int v=a[u][i].v;
			d[v]--;
			if (!d[v]) q.push(v); 
		}
	}
//	for (int i=1; i<=n; i++) cout<<b[i]<<" ";
	
	for (int i=1; i<=n; i++) te[b[i]]=s[b[i]]; //初始化最早时刻
	for (int i=1; i<=n; i++)
	{
		int u=b[i];
		for (int j=0; j<a[u].size(); j++)
		{
			int v=a[u][j].v;
			long long w=a[u][j].w;
			te[v]=min2(m, max2(te[v], te[u]+w)); //注意不超过m
		}
	}
	
	for (int i=1; i<=n; i++) printf("%lld\n", te[i]);
	return 0;
}