Pagini recente » Cod sursa (job #1963519) | Cod sursa (job #168372) | Diferente pentru teorema-chineza-a-resturilor intre reviziile 84 si 85 | Istoria paginii utilizator/patriciaxd | Cod sursa (job #1253385)
#include <fstream>
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
int gasit;
int n,m,xx,yy;
int viz[30004];
int q[30004];
struct Nod
{
int info;
int cost;
Nod *leg;
};
Nod *L[30004];
void Inserare(int nod, int adiacent,int cs)
{
Nod *p;
p=new Nod;
p->info=adiacent;
p->cost = cs;
p->leg=L[nod];
L[nod]=p;
}
long long dist[30004];
void Citire()
{
int i;
f>>n>>m>>xx>>yy;
int x1,y1,c1;
for(i=1;i<=m;i++)
{
f>>x1;
f>>y1;
f>>c1;
Inserare(x1,y1,c1);
Inserare(y1,x1,c1);
}
}
void BFS(int k)
{
int i, pr , ul, x,ct;
pr=ul=1;
viz[k]=1;
q[1]=k;
//cout<<k<<" ";
while(pr<=ul)
{
x=q[pr];
pr++;
for(Nod *p = L[x]; p ; p=p->leg)
{
i=p->info;
ct = p->cost;
if(viz[i] == 0 )
{
//cout<<i<<" ";
ul++;
q[ul]=i;
viz[i]= 1;
if(i<x) dist[i]= dist[x] - ct;
else dist[i] = dist[x]+ct;
}
if(i == yy)
{
gasit=1;
return;
}
}
}
}
int main()
{
Citire();
BFS(xx);
if(gasit == 1)
g<<dist[yy]<<"\n";
else g<<-1;
return 0;
}