Pagini recente » Cod sursa (job #817659) | Cod sursa (job #688112) | Cod sursa (job #1433162) | Cod sursa (job #929628) | Cod sursa (job #2203453)
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define NMAX 30000
using namespace std;
ifstream fi("sate.in");
ofstream fo("sate.out");
int n, m, x, y, rez;
int VIZ[NMAX+5], PRE[NMAX+5];
vector <pair <int, int> > VEC[NMAX+5];
queue <int> Q;
void citire(void)
{
int a, b, c;
fi>>n>>m>>x>>y;
for(int i=1; i<=m; i++)
{
fi>>a>>b>>c;
VEC[a].push_back({b, c});
VEC[b].push_back({a, -c});
}
}
void BFS(int src)
{
int nod, nods;
VIZ[src]=1;
memset(PRE, -1, sizeof(PRE));
Q.push(src);
while(!Q.empty())
{
nod=Q.front();
Q.pop();
for(int i=0; i<VEC[nod].size(); i++)
{
nods=VEC[nod][i].first;
if(!VIZ[nods])
{
VIZ[nods]=1;
PRE[nods]=nod;
Q.push(nods);
}
}
}
}
void rezolvare(void)
{
int nod=y;
while(PRE[nod]!=-1)
{
for(int i=0; i<VEC[nod].size(); i++)
if(VEC[nod][i].first==PRE[nod])
{
rez+=VEC[nod][i].second;
break;
}
nod=PRE[nod];
}
}
void afisare(void)
{
if(rez<0)
fo<<-rez;
else
fo<<rez;
}
int main()
{
citire();
BFS(x);
rezolvare();
afisare();
fi.close();
fo.close();
return 0;
}