pypy3(pypy3.6.1) 解法, 执行用时: 1373ms, 内存消耗: 38340K, 提交时间: 2020-06-01 20:20:35

#!/usr/bin/env python3
#
# L. Milk Scheduling
#
import sys, os, math, re, time, random, copy, shutil, itertools, functools, heapq
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict

def read_int(): return int(input())
def read_ints(): return list(map(int, input().split()))

################################################################################

n, m = read_ints()
t = [read_int() for _ in range(n)]
c = [0] * n
g = [[] for _ in range(n)]
for _ in range(m):
	u, v = read_ints()
	g[v - 1].append(u - 1)
	c[u - 1] += 1

vi = [-1] * n
q = deque()
for i in range(n):
	if c[i] == 0:
		q.append(i)
		vi[i] = t[i]
ans = 0
while q:
	u = q.popleft()
	ans = max(ans, vi[u])
	for v in g[u]:
		if vi[v] < vi[u] + t[v]:
			vi[v] = vi[u] + t[v]
			q.append(v)
print(ans)

C++11(clang++ 3.9) 解法, 执行用时: 44ms, 内存消耗: 1260K, 提交时间: 2020-05-31 11:38:39

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int a[N],tot[N],in[N];
vector<int>v[N];
queue<int>q;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		in[y]++;
	}
	for(int i=1;i<=n;i++)
	if(!in[i])
	{
		q.push(i);
		tot[i]=a[i];
	}
	int ans=-1;
	while(q.size())
	{
		int t=q.front();q.pop();
		for(int i=0;i<v[t].size();i++)
		{
			int u=v[t][i];
			if(--in[u]==0)q.push(u);
			tot[u]=max(tot[u],tot[t]+a[u]);
		}
	}
	for(int i=1;i<=n;i++)ans=max(ans,tot[i]);
	cout<<ans;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 1376K, 提交时间: 2020-05-30 11:01:04

#include<cstdio>
#include<algorithm>
#include<vector>//头文件
using namespace std;
const int MAXN=10010;
vector<int> rule[MAXN];
int t[MAXN],f[MAXN],ans=0;
int find(int x){
	if(f[x]) return f[x];
	int maxt=0;
	for(int i=0;i<rule[x].size();i++){//这里改
		maxt=max(maxt,find(rule[x][i]));
	}
	return f[x]=maxt+t[x];
}
int main(){
	int n,m,a,b;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	while(m--){
		scanf("%d%d",&a,&b);
		rule[a].push_back(b);//还有这里
	}
	for(int i=1;i<=n;i++){
		find(i);
		ans=max(ans,f[i]);
	}
	printf("%d",ans);
	return 0;
}