Cod sursa(job #2018280)

Utilizator BovisioNitica Ionut Bogdan Bovisio Data 4 septembrie 2017 12:06:56
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
//Nitica Ionut Bogdan
//04.09.2017
//Sate - InfoArena - http://www.infoarena.ro/problema/sate

#include <cstdio>
#include <queue>

using namespace std;

int n,m,x,y,c[10000][10000],viz[10000],sum = 0;

queue < int > q;

void Read()
{
    int aux1,aux2,co;
    freopen("sate.in","r",stdin);
    freopen("sate.out","w",stdout);
    scanf("%i %i %i %i",&n,&m,&x,&y);
    for(int i=1;i<=m;i++)
    {
        scanf("%i %i %i",&aux1,&aux2,&co);
        c[aux1][aux2] = c[aux2][aux1] =co;
    }
}

void BFS(int nod)
{
    viz[nod] = 1;
    q.push(nod);
    while(!q.empty() && q.front() != y)
    {
        for(int i=1;i<=n;i++)
        {
            if(viz[i] == 0 && c[q.front()][i] != 0)
            {
                if(q.front() < i)
                {
                    sum += c[q.front()][i];
                }
                else if(q.front() > i)
                {
                    sum -= c[q.front()][i];
                }
                viz[i] = 1;
                q.push(i);
            }
        }
        q.pop();
    }

}

int main()
{
    Read();
    BFS(x);
    printf("%i",sum);
    return 0;
}