Codeforces #77 Volleyball

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define REP(k,a) for(int k=0; k < (a); ++k)

int main()
{
    int n,m,S,E,tmp1,tmp2,tmp3;
    cin >> n >> m >> S >> E;
    --S;
    --E;
    vector<vector<pair<int, int> > > v(n);
    vector<vector<int> > a(n);
    vector<pair<int,int> > t(n);
    REP(i,m)
    {
        cin >> tmp1 >> tmp2 >> tmp3;
        --tmp1;
        --tmp2;
        tmp3;
        v[tmp1].push_back(make_pair(tmp2,tmp3));
        v[tmp2].push_back(make_pair(tmp1,tmp3));
    }
    REP(i,n)
    {
        cin >> t[i].first >> t[i].second ;
    }
    REP(i,n)
    {//which nodes are not further than t[i].first
        int max_dist=t[i].first+1;
        vector<int> d(n,max_dist);
        set<pair<int,int> > s;
        s.insert(make_pair(0,i));
        d[i]=0;
        while(!s.empty())
        {
            int actN=s.begin()->second;
            a[i].push_back(actN);
            int actD=s.begin()->first;
            s.erase(s.begin());
            REP(j,v[actN].size())
            {
                if(actD+v[actN][j].second<d[v[actN][j].first])
                {
                    if(d[v[actN][j].first]<max_dist)
                    {
                        s.erase(s.find(make_pair(d[v[actN][j].first],v[actN][j].first)));
                    }
                    s.insert(make_pair(actD+v[actN][j].second,v[actN][j].first));
                    d[v[actN][j].first]=actD+v[actN][j].second;
                }
            }
        }
    }
    const LL maxLL=1000000000000000LL;
    vector<LL> c(n,maxLL);
    c[S]=0;
    set<pair<LL,int> > s;
    s.insert(make_pair(0,S));
    while(!s.empty())
    {
        int actN=s.begin()->second;
        LL actC=s.begin()->first;
        if(actN==E)
        {
            cout << actC << endl;
            return 0;
        }
        s.erase(s.begin());
        REP(i,a[actN].size())
        {
            if(actC+t[actN].second<c[a[actN][i]])
            {
                if(c[a[actN][i]]<maxLL)
                {
                    s.erase(s.find(make_pair(c[a[actN][i]],a[actN][i])));
                }
                s.insert(make_pair(actC+t[actN].second,a[actN][i]));
                c[a[actN][i]]=actC+t[actN].second;
            }
        }
    }
    cout << -1 << endl;
    return 0;
}