codevs 1088 神经网络

bfs。语文题。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define maxv 150

#define maxe 100500

using namespace std;

struct edge

{

    int v,w,nxt;

}e[maxe];

queue <int> q;

int n,m,c[maxv],u[maxv],nume=,g[maxv],x,y,z,ot[maxv];

bool vis[maxv];

void addedge(int u,int v,int w)

{

    e[++nume].v=v;

    e[nume].w=w;

    e[nume].nxt=g[u];

    g[u]=nume;

}

void bfs()

{

    while (!q.empty())

    {

        int head=q.front();q.pop();

        if (c[head]>)

        {

            for (int i=g[head];i;i=e[i].nxt)

            {

                int v=e[i].v;

                c[v]+=e[i].w*c[head];

                if (!vis[v])

                {

                    c[v]-=u[v];

                    vis[v]=true;q.push(v);

                }

            }

        }

        vis[head]=false;

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=;i<=n;i++)

    {

        scanf("%d%d",&c[i],&u[i]);

        if (c[i]!=) q.push(i);

    }

    for (int i=;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&z);

        ot[x]++;

        addedge(x,y,z);

    }

    bfs();

    int flag=;

    for (int i=;i<=n;i++)

    {

        if ((!ot[i]) && (c[i]>))

        {

            flag=;

            printf("%d %d\n",i,c[i]);

        }

    }

    if (!flag) printf("NULL\n");

    return ;

}