Cod sursa(job #2369927)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 6 martie 2019 09:49:47
Problema Sate Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("sate.in");
ofstream fout("sate.out");

const int NMAX=30005;

vector<int> Ad[NMAX],Cost[NMAX];

int n,m,x,y;
int vis[NMAX],dist[NMAX];
int total;

void Read()
{
    int i,j,a,b,c;
    fin>>n>>m>>x>>y;
    for(i=1; i<=m; ++i)
    {
        fin>>a>>b>>c;
        Ad[a].push_back(b);
        Ad[b].push_back(a);
        Cost[a].push_back(c);
        Cost[b].push_back(c);
    }
}

bool found=false;

void DFS(int x)
{
    int i,w;
    vis[x]=1;
    for(i=0; i<Ad[x].size() && found==false; ++i)
        if(!vis[Ad[x][i]])
        {
            w=Ad[x][i];
            if(w>x)
                dist[w]=dist[x]+Cost[x][i];
            else dist[w]=dist[x]-Cost[x][i];
            if(w!=y)
                DFS(w);
            else found=true;
        }
}

void Do()
{
    int i,j;
    DFS(x);
    fout<<dist[y];
}

int main()
{
    Read();
    Do();
    return 0;
}