Pagini recente » Cod sursa (job #1277625) | Cod sursa (job #2951353) | Cod sursa (job #2018639) | Autentificare | Cod sursa (job #1389664)
#include <iostream>
#include <fstream>
#include <queue>
#include <cstdio>
#include <cstdlib>
using namespace std;
FILE *f = fopen("sate.in", "r");
FILE *g = fopen("sate.out","w");
vector <int> vf[30001], pond[30001];
int viz[30001], sum[30001];
int n, m, x,y;
char s[100];
void citeste()
{
int a,b, pondere;
fgets(s,100,f);
sscanf(s, "%d%d%d%d", &n,&m,&x,&y);
for(int i = 0; i < m; i++)
{
fgets(s, 100, f);
sscanf(s,"%d%d%d", &a, &b, &pondere);
//cout<<a<<' '<<b<<' '<<pondere<<'\n';
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.front();
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 (sum[y] > 0)
return ;
}
}
}
}
int main()
{
citeste();
bf(x);
fprintf(g, "%d", sum[y]);
return 0;
}