Pagini recente » Cod sursa (job #540028) | Cod sursa (job #1718405) | Rating Nazare Elena (elena25) | Monitorul de evaluare | Cod sursa (job #1461285)
/*#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
long n,m,x,y,q,w,c,viz[30005],cost;
struct gr
{
long r,c;
}punct,nod;
vector<gr>a[30005];
queue<gr> coada;
void bfs()
{
punct.r = x;
punct.c = 0;
coada.push(punct);
viz[x]=1;
while(!coada.empty() && viz[y]==0)
{
nod = coada.front();
coada.pop();
viz[nod.r]=1;
for(int i=0;i<a[nod.r].size();i++)
{
if(viz[a[nod.r][i].r]==0)
{
viz[a[nod.r][i].r]=1;
cost = cost + a[nod.r][i].c;
coada.push(a[nod.r][i]);
}
}
//cost = cost - nod.c;
}
}
int main()
{
ifstream in("sate.in");
ofstream out("sate.out");
in >> n >> m >> x >> y;
for(int i=0;i<m;i++)
{
in >> q >> w >> c;
punct.r = w;
punct.c = c;
a[q].push_back(punct);
punct.r = q;
punct.c = -c;
a[w].push_back(punct);
}
bfs();
out << cost;
return 0;
}
*/
#include <fstream>
#include <vector>
#include <string.h>
#define dim 30005
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
int d[dim],i,j,n,m,x,y,a,b,c;
vector <pair<int,int> >v[dim];
void bfs(int nod)
{
int i;
int T=v[nod].size();
for(i=0;i<T;i++)
if(d[v[nod][i].first]==0)
{
int r=v[nod][i].first;
int w=v[nod][i].second;
d[r]=d[nod]+w;
bfs(r);
}
}
int main()
{f>>n>>m>>x>>y;
for(i=1;i<=m;i++){
f>>a>>b>>c;
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,-c));
}
bfs(x);
if(d[y]<0)
g<<-d[y];
else
g<<d[y];
return 0;
}