Pagini recente » Cod sursa (job #2023338) | Cod sursa (job #2017837) | Cod sursa (job #9957) | Cod sursa (job #1127963) | Cod sursa (job #900318)
Cod sursa(job #900318)
#include <fstream>
#include <queue>
#include <vector>
#define NMAX 30002
using namespace std;
ifstream fin("sate.in");
ofstream fout("sate.out");
void bfs();
void citire();
struct muchie{int vf,cost;};
vector <muchie> L[NMAX];
queue <int> C;
int dmin[NMAX],viz[NMAX],s,f,n,m;
int main()
{
citire();
bfs();
}
void citire()
{
int i,c,x,y;
muchie aux;
fin>>n>>m>>s>>f;
for(i=1;i<=m;i++)
{
fin>>x>>y>>c;
aux.vf=y;aux.cost=c;
L[x].push_back(aux);
aux.vf=x;
L[y].push_back(aux);
}
}
void bfs()
{
int i,j,vfmin;
viz[s]=1;
for(i=0;i<L[s].size();i++)
{
dmin[L[s][i].vf]=L[s][i].cost; C.push(L[s][i].vf);
viz[L[s][i].vf]=1;
}
dmin[s]=0;
while(!C.empty())
{
vfmin=C.front();
C.pop();
for(j=0;j<L[vfmin].size();j++)
{
if(L[vfmin][j].vf>vfmin) dmin[L[vfmin][j].vf]=dmin[vfmin]+L[vfmin][j].cost;
else dmin[L[vfmin][j].vf]=dmin[vfmin]-L[vfmin][j].cost;
if(viz[L[vfmin][j].vf]==0)
{
C.push(L[vfmin][j].vf);
viz[L[vfmin][j].vf]=1;
}
}
}
if(dmin[f]==0) fout<<-1;
else
fout<<dmin[f];
}