Pagini recente » Cod sursa (job #241587) | Cod sursa (job #1514943) | Cod sursa (job #714914) | Cod sursa (job #2952940) | Cod sursa (job #68045)
Cod sursa(job #68045)
// sate O(M + N)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define NMax 30005
#define pb push_back
#define mp make_pair
#define f first
#define s second
int N, M, X, Y, S[NMax], q[NMax];
vector< pair<int, int> > G[NMax];
int modul(int X)
{ if (X < 0) return -X; return X; }
int main(void)
{
int i, u, v, D, ql, qr;
vector< pair<int, int> >::iterator it;
freopen("sate.in", "r", stdin);
freopen("sate.out", "w", stdout);
scanf("%d %d %d %d", &N, &M, &X, &Y);
for (i = 1; i <= M; i++)
{
scanf("%d %d %d", &u, &v, &D);
G[u].pb( mp(v, D) );
G[v].pb( mp(u, D) );
}
memset(S, -1, sizeof(S));
for (q[ql=qr=0]=X, S[X] = 0; qr <= ql; qr++)
for (it = G[q[qr]].begin(); it != G[q[qr]].end(); it++)
if (S[it->f] == -1)
{
q[++ql] = it->f;
if ((it->f - q[qr]) * (it->f - X) < 0 ||
(X - q[qr]) * (X - it->f) < 0)
S[it->f] = modul(S[q[qr]] - it->s);
else
S[it->f] = S[q[qr]] + it->s;
}
if (S[Y] == -1)
printf("NO\n");
else
printf("%d\n", S[Y]);
return 0;
}