Pagini recente » Cod sursa (job #2639492) | Cod sursa (job #1655608) | Cod sursa (job #3279386) | Cod sursa (job #230399) | Cod sursa (job #1698922)
#include <iostream>
#include <fstream>
#include <bitset>
#include <queue>
#include <vector>
#define maxN 30003
using namespace std;
ifstream fin("sate.in");
ofstream fout("sate.out");
int n,m,x,y,d[maxN];
vector < pair <int,int> > v[maxN];
bitset <maxN> inQ;
queue <int> Q;
void readData()
{
fin>>n>>m>>x>>y;
while (m--)
{
int a,b,c;
fin>>a>>b>>c;
v[a].push_back(make_pair(b,c));
v[b].push_back(make_pair(a,-c));
}
}
void BFS(int x)
{
Q.push(x);
inQ[x]=1;
d[x]=0;
while (!Q.empty())
{
x=Q.front();
Q.pop();
for (int i=0; i<v[x].size(); ++i)
if (!inQ[v[x][i].first])
{
d[v[x][i].first]=d[x]+v[x][i].second;
Q.push(v[x][i].first);
inQ[v[x][i].first]=1;
}
}
fout<<d[y];
}
int main()
{
readData();
BFS(x);
return 0;
}