Cod sursa(job #593280)

Utilizator blastoiseZ.Z.Daniel blastoise Data 1 iunie 2011 22:30:07
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <deque>

#define MAX 30001

using namespace std;

struct cost
{
    short nod;
    int cost;
}*v[MAX];

short grad[MAX];
int drum[MAX];
char use[MAX];
deque <short> q;
int X,Y;

inline void swap(int &x,int &y)
{
    int z=x;
    x=y;
    y=z;
}

inline void bf(int nod)
{
    for(int i=0;i<grad[nod];i++)
        if(!use[v[nod][i].nod])
        {
            use[v[nod][i].nod]=1;
            drum[v[nod][i].nod]=drum[nod]+v[nod][i].cost;
            if(v[nod][i].nod==Y) return;
            q.push_back(v[nod][i].nod);
        }

    if(q.size())
    {
        nod=q.front();
        q.pop_front();
        bf(nod);
    }
}

int main()
{
    int M,N,x,y,d;

    ifstream in;

    memset(grad,0,sizeof(grad));

    in.open("sate.in");

    in>>N>>M>>X>>Y;

    for(;M;--M)
    {
        in>>x>>y>>d;
        grad[x]++;
        grad[y]++;
    }

    in.close();

    for(int i=1;i<=N;i++)
        v[i]=(cost *)malloc(grad[i]*sizeof(cost));

    memset(grad,0,sizeof(grad));

    in.open("sate.in");

    in>>N>>M>>X>>Y;

    for(;M;--M)
    {
        in>>x>>y>>d;

        if(x>y) swap(x,y);

        v[x][grad[x]].nod=y;
        v[y][grad[y]].nod=x;
        v[x][grad[x]++].cost=d;
        v[y][grad[y]++].cost=-d;
    }

    in.close();

    memset(drum,0,sizeof(drum));
    memset(use,0,sizeof(use));
    use[X]=1;

    bf(X);

    ofstream out;

    out.open("sate.out");

    out<<drum[Y]<<'\n';

    out.close();

    return 0;
}