【题解】LuoGu6145：[USACO20FEB]Timeline G

原题传送门
因为原图是一个DAG，所以直接跑一个拓扑
但是我一开始是用跑最长路的方法做的，虽然用$spfa$也可以
但是我用了堆优$dijk$，就错掉了，所以这里抛出一个问题，为什么堆优不行？

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
struct Edge{
	int to, next, len;
}edge[maxn << 1];
queue <int> q;
int num, head[maxn], n, m, M, dis[maxn], d[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y, int z){ edge[++num] = (Edge){y, head[x], z}, head[x] = num; }

int main(){
	freopen("timeline.in", "r", stdin);
	freopen("timeline.out", "w", stdout);
	n = read(), M = read(), m = read();
	for (int i = 1; i <= n; ++i){
		int x = read();
		addedge(0, i, x);
		++d[i];
	}
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read(), z = read();
		addedge(x, y, z);
		++d[y];
	}
	q.push(0);
	while (!q.empty()){
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = edge[i].next){
			int v = edge[i].to;
			dis[v] = max(dis[v], dis[u] + edge[i].len);
			--d[v];
			if (d[v] == 0) q.push(v);
		}
	}
	for (int i = 1; i <= n; ++i) printf("%d\n", dis[i]);
	return 0;
}