Cod sursa(job #1832211)

Utilizator mateigabriel99Matei Gabriel mateigabriel99 Data 19 decembrie 2016 16:45:29
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>

#define NMax 30001

using namespace std;

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

int N,M,X,Y,x,y,z;
vector< pair<int,int> > Graf[NMax];
bool mark[NMax];
int Sol[100030];

void Read()
{
    fin>>N>>M>>X>>Y;
    for(int i=1;i<=M;i++)
    {
        fin>>x>>y>>z;
        Graf[x].push_back(make_pair(y,z));
        Graf[y].push_back(make_pair(x,-z));
    }
}

void DFS(int nod)
{
    mark[nod]=true;
    for(vector< pair<int,int> >::iterator it=Graf[nod].begin();it!=Graf[nod].end();it++)
        if(!mark[it->first])
        {
            Sol[it->first]=Sol[nod]+it->second;
            DFS(it->first);
            if(it->first==Y)
            {
                fout<<Sol[Y];
                exit(0);
            }
        }
}

int main()
{
    Read();
    DFS(X);
    fout<<Sol[Y];
    return 0;
}