Cod sursa(job #528312)

Utilizator david_raucaRauca Ioan David david_rauca Data 2 februarie 2011 16:05:54
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

#define DIM 30001
#define INF 0x3f3f3f3f

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

int n, m, x, y;
bool s[DIM];

vector<vector<pair<int, int> > > G;

void Read();
void Drum( int x, int d);

int main()
{
    Read();
    Drum( x, 0 );
    
    fin.close();
    fout.close();
    
    return 0;
}

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

void Drum(int x, int d)
{
     if( x == y )
     {
         fout << d;
         return;
     }
     
     for( int i = 0; i < G[x].size(); ++i )
          if( !s[G[x][i].first] )
          {
              s[G[x][i].first] = true;
              Drum( G[x][i].first, d + G[x][i].second );
          }
}