Cod sursa(job #1254031)

Utilizator cozmin97Gemene Cozmin cozmin97 Data 2 noiembrie 2014 09:20:04
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>

using namespace std;
ofstream g("sate.out");
int gasit;
int n,m,x,y;
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()
{
    ifstream f("sate.in");
    int i;
    f>>n>>m>>x>>y;
    int x1,y1,c1;
    for(i=1;i<=m;i++)
    {
        f>>x1>>y1>>c1;
        Inserare(x1,y1,c1);
        Inserare(y1,x1,c1);
    }
}

void Rez(int k)
{
    int i, pr , ul, j,ct;
    pr=ul=1;
    viz[k]=1;
    q[1]=k;
    while(pr<=ul)
    {
        j=q[pr];
        pr++;
        for(Nod *p = L[j]; p ; p=p->leg)
        {
            i=p->info;
            ct = p->cost;

            if(viz[i] == 0 )
            {
                ul++;
                q[ul]=i;
                viz[i]= 1;

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

int main()
{
    Citire();
    Rez(x);
    if(gasit == 1)
        g<<dist[y]<<"\n";
    else g<<-1;
    return 0;
}