Pagini recente » Cod sursa (job #418710) | Cod sursa (job #160473) | Cod sursa (job #2494369) | Cod sursa (job #1530653) | Cod sursa (job #1169720)
#include<cstdio>
#include<vector>
using namespace std;
vector<int>cost[100010],v[100010];
int costdrum,nod1,nod2,n,m,plecare,sosire,viz[50000],rasp[50000],i,coada[50000];
int bfs(int nod)
{
int ic=1;
int sf=1;
coada[ic]=nod;
while(ic<=sf)
{
for(i=0;i<=v[coada[ic]].size()-1;i++)
{
if(!viz[v[coada[ic]][i]])
{
if(v[coada[ic]][i]>coada[ic])
rasp[v[coada[ic]][i]]=rasp[coada[ic]]+cost[coada[ic]][i];
else
rasp[v[coada[ic]][i]]=rasp[coada[ic]]-cost[coada[ic]][i];
coada[++sf]=v[coada[ic]][i];
viz[v[coada[ic]][i]]=1;
if(v[coada[ic]][i]==sosire)
return 0;
}
}
++ic;
}
}
int main()
{
freopen("sate.in","r",stdin);
freopen("sate.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&plecare,&sosire);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&nod1,&nod2,&costdrum);
v[nod1].push_back(nod2);
v[nod2].push_back(nod1);
cost[nod1].push_back(costdrum);
cost[nod2].push_back(costdrum);
}
viz[plecare]=1;
bfs(plecare);
printf("%d",rasp[sosire]);
}