Pagini recente » Cod sursa (job #618263) | Cod sursa (job #1714912) | Cod sursa (job #371381) | Cod sursa (job #3255255) | Cod sursa (job #478098)
Cod sursa(job #478098)
#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;
}