Cod sursa(job #478098)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 17 august 2010 13:42:25
Problema Sate Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
typedef struct{
  int nod,cost;
} elem;
bool viz[30001];
elem d1,d2;
int drum[30001],a,b,distanta,x,y,i,ok,m,n;
vector<elem>v[30001];
queue<int>c;
int main()
{
    ifstream fi("sate.in");
    ofstream fo("sate.out");
    fi>>n>>m>>x>>y;
    for(i=1;i<=m;i++)
    {
      fi>>a>>b>>distanta;
      d1.nod=b; d1.cost=distanta;
      d2.nod=a; d2.cost=-distanta;
      v[a].push_back(d1);
      v[b].push_back(d2);
    }
    a=x; b=y;
    c.push(x);
    viz[x]=1;
    ok=0;
    while(!c.empty() and !ok)
    {
      x=c.back();
      c.pop();
      m=v[x].size();
      for(i=0;i<m;i++)
      if(!viz[v[x][i].nod])
      {
        drum[v[x][i].nod]=drum[x]+v[x][i].cost;
        if(v[x][i].nod==y) { ok=1; break;   }
        viz[v[x][i].nod]=1;
        c.push(v[x][i].nod);
      }
    }
    if(a<=b)
    fo<<drum[y]<<"\n";
    else fo<<-drum[y]<<"\n";
    fo.close();
    return 0;
}