Cod sursa(job #1253385)

Utilizator Laura.miLaura Mitrache Laura.mi Data 1 noiembrie 2014 10:54:42
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>

using namespace std;

ifstream f("sate.in");
ofstream g("sate.out");
int gasit;
int n,m,xx,yy;
int viz[30004];
int q[30004];
struct Nod
{
    int info;
    int cost;
    Nod *leg;
};
Nod *L[30004];


void Inserare(int nod, int adiacent,int cs)
{
    Nod *p;
    p=new Nod;
    p->info=adiacent;
    p->cost = cs;
    p->leg=L[nod];
    L[nod]=p;
}
long long dist[30004];

void Citire()
{
    int i;
    f>>n>>m>>xx>>yy;
    int x1,y1,c1;
    for(i=1;i<=m;i++)
    {
        f>>x1;
        f>>y1;
        f>>c1;
        Inserare(x1,y1,c1);
        Inserare(y1,x1,c1);
    }
}

void BFS(int k)
{
    int i, pr , ul, x,ct;
    pr=ul=1;
    viz[k]=1;
    q[1]=k;
    //cout<<k<<" ";

    while(pr<=ul)
    {
        x=q[pr];
        pr++;
        for(Nod *p = L[x]; p ; p=p->leg)
        {
            i=p->info;
            ct = p->cost;

            if(viz[i] == 0 )
            {
                //cout<<i<<" ";
                ul++;
                q[ul]=i;
                viz[i]= 1;

                if(i<x) dist[i]= dist[x] - ct;
                else dist[i] = dist[x]+ct;
            }
            if(i == yy)
            {
                gasit=1;
                return;
            }

        }
    }
}

int main()
{
    Citire();
    BFS(xx);
    if(gasit == 1)
    g<<dist[yy]<<"\n";

else g<<-1;
    return 0;
}