Pagini recente » Cod sursa (job #354123) | Cod sursa (job #345311) | Cod sursa (job #2087810) | Cod sursa (job #1073393) | Cod sursa (job #2680750)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("sate.in");
ofstream out("sate.out");
vector <pair<int,int>> graf[30001];
stack <pair<int,int>> ms;
int n,m,st,fn,vf[30001],dist;
void citire()
{
in>>n>>m>>st>>fn;
for(int i=1;i<=m;i++)
{
int x,y,z;
in>>x>>y>>z;
graf[x].push_back({y,z});
graf[y].push_back({x,z});
}
}
int dfs()
{
ms.push({st,0});
vf[st]=1;
while(!ms.empty())
{
int nod=ms.top().first;
ms.pop();
int nr=graf[nod].size();
for(int i=0;i<nr;i++)
{
int nextnod=graf[nod][i].first,drum=graf[nextnod][i].second;
if(vf[nextnod]==0)
{
vf[nextnod]=1;
if(nextnod<nod)
dist-=drum;
else
dist+=drum;
if(nextnod==fn)
return dist;
ms.push({nextnod,drum});
}
}
}
}
int main()
{
citire();
out<<dfs();
return 0;
}