Pagini recente » Cod sursa (job #1389699) | Cod sursa (job #487463) | Cod sursa (job #1378134) | Cod sursa (job #2601324) | Cod sursa (job #1389614)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("sate.in");
vector <int> vf[30001], pond[30001];
int viz[30001], sum[30001];
int n, m, x,y;
void citeste()
{
int a,b, pondere;
f>>n>>m>>x>>y;
for(int i = 0; i < m; i++)
{
f>>a>>b>>pondere;
vf[a].push_back(b);
vf[b].push_back(a);
pond[a].push_back(pondere);
pond[b].push_back(pondere);
}
}
void bf(int rad)
{
queue <int> coada;
coada.push(rad);
viz[rad] = 1;
while(!coada.empty() && sum[y] == 0)
{
rad = coada.back();
coada.pop();
int dim = vf[rad].size();
for(int i = 0; i < dim && sum[y]==0; i++)
{
if(!viz[vf[rad][i]])
{
coada.push(vf[rad][i]);
viz[vf[rad][i]] = 1;
if(rad < vf[rad][i])
sum[vf[rad][i]] = sum[rad] + pond[rad][i];
else
sum[vf[rad][i]] = sum[rad] - pond[rad][i];
if (vf[rad][i] == y)
return ;
}
}
}
}
int main()
{
citeste();
bf(x);
cout<<sum[y];
return 0;
}