Submission #1383145

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N, M, K;
int S, T;
vector<P> G[30000];
int X[101], F[101];
int D[2][30000];

long long f(int x) {
  if (x <= 0) return 0;
  return F[upper_bound(X, X+K+1, x)-X-1];
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M >> K >> S >> T;
  rep(i, M) {
    int a, b, c;
    cin >> a >> b >> c;
    G[a].pb(P(b, c));
    G[b].pb(P(a, c));
  }
  rep(i, K) cin >> X[i] >> F[i];
  X[K] = INF;

  rep(k, 2) {
    rep(i, N) D[k][i] = INF;
    int s = S;
    if (k == 1) s = T;
    priority_queue<P, vector<P>, greater<P> > q;
    D[k][s] = 0;
    q.push(P(0, s));
    while (!q.empty()) {
      int r = q.top()._1,
          x = q.top()._2;
      q.pop();
      if (D[k][x] < r) continue;

      for (auto p : G[x]) {
        int t = p._1, d = p._2;
        if (D[k][t] > r+d) {
          D[k][t] = r+d;
          q.push(P(D[k][t], t));
        }
      }
    }
  }
  long long m = (1LL<<60);
  rep(k, N) {
    m = min(m, f(D[0][k]) + f(D[1][k]));
  }
  cout << m << "\n";
  return 0;
}

Submission Info

Judge Result