Pagini recente » Rezultatele filtrării | Cod sursa (job #638457)
Cod sursa(job #638457)
#include <cstdio>
#include <vector>
#include <deque>
#include <stack>
#define NMAX 30000
using namespace std;
typedef vector< pair<int, int> > lista;
vector<lista> a(NMAX);
stack< pair<int, int> > s;
deque< pair<int, int> > l;
int viz[NMAX];
int N, M, X, Y;
int main()
{
pair<int, int>curent;
int i, x, y, d, ok, tata, dist;
lista::iterator it;
freopen("sate.in", "r", stdin);
freopen("sate.out", "w", stdout);
scanf("%d %d %d %d", &N, &M, &X, &Y);
for(i=0;i<M;++i)
{
scanf("%d %d %d", &x, &y, &d);
a[x].push_back(make_pair(y, d));
a[y].push_back(make_pair(x, d));
}
s.push(make_pair(X, 0));
while(!s.empty())
{
curent = s.top();
s.pop();
l.push_front(curent);
viz[curent.first] = 1;
if(curent.first == Y)
{
break;
}
ok = 0;
for(it=a[curent.first].begin();it!=a[curent.first].end();++it)
{
if(!viz[it->first])
{
ok = 1;
s.push(*it);
}
}
if(!ok)
l.pop_front();
}
curent = l.back();
l.pop_back();
tata = curent.first;
dist = 0;
while(!l.empty())
{
curent = l.back();
l.pop_back();
if(tata < curent.first)
{
dist += curent.second;
}
else
{
dist -= curent.second;
}
tata = curent.first;
}
if(dist < 0)
{
dist *= -1;
}
printf("%d", dist);
return 0;
}