Pagini recente » Cod sursa (job #569706) | Cod sursa (job #2100590) | Cod sursa (job #979566) | Cod sursa (job #2263034) | Cod sursa (job #802294)
Cod sursa(job #802294)
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#define pb push_back
#define mkp make_pair
using namespace std;
bool sel[100005];
int nv[100005],n,m,X,Y,i,x,y,d;
vector <pair <int, int> > a[100005];
queue <int> Q;
ifstream f("sate.in");
ofstream g("sate.out");
void bf(int x)
{
vector <pair <int, int> > :: iterator it;
int nod;
pair <int, int> z;
Q.push(x);
sel[x]=true;
nv[x]=0;
while (!Q.empty()) {
nod=Q.front();
for (it=a[nod].begin();it!=a[nod].end();it++) {
z=*it;
if (!sel[z.first])
{
Q.push(z.first);
nv[z.first]=nv[nod]+z.second;
sel[z.first]=true;
}
}
Q.pop();
}
}
int main()
{
f>>n>>m>>X>>Y;
for (i=1;i<=m;i++) {
f>>x>>y>>d;
a[x].pb(mkp(y,d));
a[y].pb(mkp(x,-d));
}
bf(X);
g<<nv[Y];
return 0;
}