C++14(g++5.4) 解法, 执行用时: 97ms, 内存消耗: 7136K, 提交时间: 2019-10-07 12:11:56

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ans=0,n,m,i,x,y,dp[100005],a[100005],b[100005];
const ll mod=1e9+7;
vector<ll>s[100005];
ll M(ll x){return x>=mod?x-mod:x;}
void dfs(int p)
{
	ll i,v;
	if(dp[p]!=-1)return;
	dp[p]=0;
	for(i=0;i<s[p].size();i++)
	{
		v=s[p][i];
		dfs(v);
		dp[p]=M(dp[p]+dp[v]);
		dp[p]=M(dp[p]+b[v]);
	}
	ans=(ans+dp[p]*a[p])%mod;
}
int main()
{
	while(scanf("%lld%lld",&n,&m)!=EOF)
	{
		ans=0;
		for(i=1;i<=n;i++)s[i].clear(),dp[i]=-1,scanf("%lld%lld",&a[i],&b[i]);
		for(i=1;i<=m;i++)
		{
			scanf("%lld%lld",&x,&y);
			s[x].push_back(y);
		}
		for(i=1;i<=n;i++)if(dp[i]==-1)dfs(i);
		printf("%lld\n",ans);
	}
	return 0;
 } 

C++11(clang++ 3.9) 解法, 执行用时: 96ms, 内存消耗: 7928K, 提交时间: 2019-10-08 21:39:42

#include<bits/stdc++.h>
#define MOD 1000000007
#define MAX 100005
using namespace std;
typedef long long lld;
lld a[MAX],b[MAX],c[MAX]={0},d[MAX]={0};
vector <int > G[MAX];
int main()
{
	int n,m;
	lld u,v;
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%lld%lld",a+i,b+i);
	for(int i=1;i<=m;i++) {
		scanf("%lld%lld",&u,&v);
		G[u].push_back(v);
		d[v]++;
	}
	queue<int > q;
	for(int i=1;i<=n;i++) {
		if(d[i]==0) q.push(i);
	}
	lld ans=0;
	while(!q.empty()) {
		u=q.front();
		q.pop();
		ans+=(c[u]*b[u])%MOD;
		ans%=MOD;
		c[u]+=a[u];
		c[u]%=MOD;
		for(int i=0;i<G[u].size();i++) {
			v=G[u][i];
			c[v]+=c[u];
			c[v]%=MOD;
			d[v]--;
			if(d[v]==0) q.push(v);
		}
	}
	cout<<ans<<endl;
	return 0;
}