Pagini recente » Cod sursa (job #15199) | Cod sursa (job #296104) | Cod sursa (job #2067483) | Cod sursa (job #2764458) | Cod sursa (job #757542)
Cod sursa(job #757542)
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 100005
#define maxm 1000005
using namespace std ;
vector <int> vecini[maxn] ;
vector <int> distanta[maxn] ;
int n,m,x,y ;
int dist[maxn] ;
int coada[maxn] ;
bool mare ;
void bf(int nod)
{
int len = 1 ;
coada[1] = nod ;
for(int j=1;j<=len;++j)
{
int nod_act = coada[j];
for(size_t i=0;i<vecini[nod_act].size();++i)
{
if( dist[ vecini[ nod_act ][i] ] == 0 )
{
++ len ;
coada[len] = vecini[ nod_act ][i] ;
if( mare == true )
{
if( vecini[nod_act][i] < nod_act )
dist[ vecini[ nod_act ][i] ] = dist[nod_act] + distanta[nod_act][ i ] ;
else
dist[ vecini[ nod_act ][i] ] = dist[nod_act] - distanta[nod_act][ i ] ;
}
else
{
if( vecini[nod_act][i] < nod_act )
dist[ vecini[ nod_act ][i] ] = dist[nod_act] - distanta[nod_act][ i ] ;
else
dist[ vecini[ nod_act ][i] ] = dist[nod_act] + distanta[nod_act][ i ] ;
}
}
}
}
}
int main()
{
freopen("sate.in","r",stdin);
freopen("sate.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&x,&y);
for(int i=1;i<=m;++i)
{
int a,b,d ;
scanf("%d%d%d",&a,&b,&d);
vecini[a].push_back(b) ;
vecini[b].push_back(a) ;
distanta[a].push_back(d) ;
distanta[b].push_back(d) ;
}
return 0 ;
bf(x) ;
printf("%d\n",dist[y]);
return 0;
}