Cod sursa(job #1461285)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 15 iulie 2015 12:28:09
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb

/*#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

long n,m,x,y,q,w,c,viz[30005],cost;
struct gr
{
    long r,c;
}punct,nod;
vector<gr>a[30005];
queue<gr> coada;
void bfs()
{

   punct.r = x;
   punct.c = 0;
   coada.push(punct);
   viz[x]=1;
   while(!coada.empty() && viz[y]==0)
   {

       nod = coada.front();
       coada.pop();
        viz[nod.r]=1;
       for(int i=0;i<a[nod.r].size();i++)
       {
           if(viz[a[nod.r][i].r]==0)
           {
               viz[a[nod.r][i].r]=1;
                cost = cost + a[nod.r][i].c;
               coada.push(a[nod.r][i]);
           }
       }
              //cost = cost - nod.c;
   }

}

int main()
{
   ifstream in("sate.in");
   ofstream out("sate.out");
   in >> n >> m >> x >> y;
   for(int i=0;i<m;i++)
   {
       in >> q >> w >> c;
       punct.r = w;
       punct.c = c;
       a[q].push_back(punct);
       punct.r = q;
       punct.c = -c;
       a[w].push_back(punct);
   }
   bfs();
      out << cost;
    return 0;
}
*/

#include <fstream>
#include <vector>
#include <string.h>
#define dim 30005
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
int d[dim],i,j,n,m,x,y,a,b,c;
vector <pair<int,int> >v[dim];

void bfs(int nod)
{
    int i;
    int T=v[nod].size();
    for(i=0;i<T;i++)
        if(d[v[nod][i].first]==0)
        {
            int r=v[nod][i].first;
            int w=v[nod][i].second;
            d[r]=d[nod]+w;
            bfs(r);
        }
}
int main()
{f>>n>>m>>x>>y;
    for(i=1;i<=m;i++){
        f>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,-c));
    }
    bfs(x);
   if(d[y]<0)
        g<<-d[y];
    else
        g<<d[y];

    return 0;
}