Pagini recente » Cod sursa (job #1251640) | Cod sursa (job #2702764) | Autentificare | Cod sursa (job #532023) | Cod sursa (job #1253060)
#include <fstream>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <vector>
#define Nmax 100004
#define In "sate.in"
#define Out "sate.out"
using namespace std;
vector< pair<short,int> >Graph[Nmax];
short n,pp,ps,ok = 1;
long long sum[Nmax];
bool viz[Nmax];
char *buffer;
inline void Init_buffer()
{
ifstream f(In);
f.seekg(0,ios::end);
int lg = f.tellg();
f.seekg(0,ios::beg);
buffer = (char*)malloc(lg);
f.getline(buffer,lg,0);
f.close();
}
template <class T>
void Citeste(T &x)
{
while(*buffer<'0'||'9'<*buffer)
buffer++;
x = 0;
while('0'<=*buffer && *buffer <='9')
x = x*10+*buffer-'0',buffer++;
}
inline void Citire()
{
ifstream f(In);
int m,x,y,c;
Citeste(n);Citeste(m);
Citeste(pp);Citeste(ps);
for(;m;m--)
{
Citeste(x);Citeste(y);Citeste(c);
Graph[x].push_back(make_pair(y,c));
Graph[y].push_back(make_pair(x,-c));
}
}
inline void BFS(short nod)
{
viz[nod] = true;
queue < int > Q;
for(Q.push(nod); !Q.empty();Q.pop())
{
nod = Q.front();
for(vector< pair<short ,int> >::iterator it=Graph[nod].begin();ok &&it!=Graph[nod].end();it++)
if(viz[(*it).first]==false)
{
sum[(*it).first] = sum[nod]+(*it).second;
Q.push((*it).first);
viz[(*it).first ] = 1;
}
}
}
int main()
{
Init_buffer();
Citire();
BFS(pp);
ofstream g(Out);
g<<sum[ps]<<"\n";
g.close();
return 0;
}