csu1804

/*
csu 1804
因为define和const总出错,到现在也不明白为什么 不知道define 和 const 出来的 mod 有什么区别
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int mod = 1000000000+7;
long long ans[100000+10];
long long a[100000+10];
long long b[100000+10];
long long d[100000+10];//d[i]代表入度
vector<int>e[100000+10];
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<=n;i++)
        {
            e[i].clear();

        }
        queue<int>q;
        memset(ans,0,sizeof(ans));
        memset(d,0,sizeof(d));
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&a[i],&b[i]);
        }
        int u,v;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            e[v].push_back(u);
            d[u]++;
        }
        for(int i=1;i<=n;i++)
        {
            if(d[i]==0)
                q.push(i);
        }
        while(!q.empty())
        {
            int to=q.front();
                q.pop();
            for(int i=0;i<e[to].size();i++)
            {
                int from=e[to][i];
                ans[from]=(ans[from]+(ans[to]+b[to])%mod)%mod;
                if(--d[from]==0)
                {
                    q.push(from);
                }
            }
        }
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            sum=(sum+ans[i]*a[i]%mod)%mod;
        }
        printf("%lld
",sum);

    }
    return 0;
}

  

原文地址:https://www.cnblogs.com/lulichuan/p/6709980.html