144D - Missile Silos - CodeForces Solution

#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define repi(i, a, b) for (int i = (a), i##len = (b); i <= i##len; ++i)
#define repll(i, a, b) for (ll i = (a), i##len = (b); i <= i##len; ++i)
#define peri(i, a, b) for (int i = (a), i##len = (b); i >= i##len; --i)
#define perll(i, a, b) for (ll i = (a), i##len = (b); i >= i##len; --i)
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define cg \
  repi(i, 1, n) { g[i].clear(); }
#define x first
#define y second
#define all(x) x.begin(), x.end()
// #define sz(x) (x).size()
#define lowbit(t) t & (-t)
#define PI 3.1415926535
#define INF 0x3f3f3f3f
const ll MOD = 1e9 + 7;
int dx[8] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
template <class U, class T>
void Max(U &x, T y) {
  if (x < y) x = y;
}
template <class U, class T>
void Min(U &x, T y) {
  if (x > y) x = y;
}

template <typename T>
inline void rd(T &x) {
  x = 0;
  int w = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') w = -1;
    c = getchar();
  }
  while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  x *= w;
}

template <typename T>
inline void wt(T x) {
  static int a[65];
  int top = 0;
  do {
    a[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(a[--top] + 48);  // 48 是 '0'
}

int dcmp(double a, double b) {
  constexpr double eps = 1e-9;
  if (a - b < eps) return -1;
  if (a - b > eps) return 1;
  return 0;
}

struct int128 {
  long long hig;
  long long low;
};
// if(ans.hig==0) {
//         printf("%lld", ans.low);
//     } else {
//         printf("%lld%018lld\n", ans.hig, ans.low);
//     }
// ll p = 1e18;  //作mod用
// int128 max(int128 a, int128 b) {
//   if (a.hig > b.hig) return a;
//   if (a.hig < b.hig) return b;  //高位比较
//   if (a.low > b.low) return a;
//   if (a.low < b.low) return b;  //低位比较
//   return a;                     //相等时还要返回一个值
// }
// int128 operator+(int128 a, int128 b)  //重载运算符
// {
//   int128 k;
//   k.low = 0, k.hig = 0;
//   k.low = a.low + b.low;
//   k.hig = k.low / p + a.hig + b.hig;  //防止溢出
//   k.low %= p;
//   return k;
// }
// int128 operator*(int128 a, int b) {
//   int128 k;
//   k.low = 0, k.hig = 0;
//   k.low = a.low * b;
//   k.hig += k.low / p + b * a.hig;  //与上同理
//   k.low %= p;
//   return k;
// }

vector<int> mul_vec(const vector<int> &a, int b) {
  vector<int> c;
  int t = 0;
  for (int i = 0; i < a.size(); i++) {
    t += a[i] * b;
    c.push_back(t % 10);
    t /= 10;
  }
  while (t) {
    c.push_back(t % 10);
    t /= 10;
  }
  return c;
}

vector<int> div_vec(const vector<int> &a, int b) {
  vector<int> c;
  bool is_first = true;
  for (int i = a.size() - 1, t = 0; i >= 0; i--) {
    t = t * 10 + a[i];
    int x = t / b;
    if (!is_first || x) {
      is_first = false;
      c.push_back(x);
    }
    t %= b;
  }
  reverse(c.begin(), c.end());
  return c;
}

vector<int> max_vec(const vector<int> &a, const vector<int> &b) {
  if (a.size() > b.size()) return a;
  if (a.size() < b.size()) return b;
  if (vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend()))
    return a;
  return b;
}

void print_vec(const vector<int> &a) {
  for (int i = a.size() - 1; i >= 0; i--) {
    printf("%d", a[i]);
  }
}

inline ll qpow(ll b, ll k, int MOD) {
  ll ans = 1;
  while (k) {
    if (k & 1) {
      (ans *= b) %= MOD;
    }
    (b *= b) %= MOD;
    k >>= 1;
  }
  return ans;
}

int n, m, k;
constexpr int MAXN = 1e5 + 5;
vector<pii> g[MAXN];
pair<pii, int> e[MAXN];
int dis[MAXN];
bool vis[MAXN];
int ans;
int l;

void solve() {
  rd(n);
  rd(m);
  rd(k);
  int x, y, w;
  repi(i, 1, m) {
    rd(x);
    rd(y);
    rd(w);
    g[x].eb(y, w);
    g[y].eb(x, w);
    e[i] = {pii(x, y), w};
  }
  rd(l);
  if (l == 0) {
    wt(1);
    return;
  }

  memset(dis, INF, sizeof(dis));
  priority_queue<pii, vector<pii>, greater<pii>> q;
  q.emplace(0, k);
  dis[k] = 0;

  while (!q.empty()) {
    auto [d, u] = q.top();
    q.pop();
    if (d > dis[u]) {
      continue;
    }

    for (auto &&[v, w] : g[u]) {
      if (dis[v] > d + w) {
        dis[v] = d + w;
        q.emplace(dis[v], v);
      }
    }
  }

  repi(i, 1, n) {
    if (dis[i] == l) {
      ++ans;
    }
  }

  repi(i, 1, m) {
    auto [xy, w] = e[i];
    auto [x, y] = xy;
    if (dis[x] >= l && dis[y] >= l) {
      continue;
    }
    if (dis[x] < l && dis[y] >= l) {
      if (dis[x] + w > l) {
        ++ans;
      }
    }
    if (dis[y] < l && dis[x] >= l) {
      if (dis[y] + w > l) {
        ++ans;
      }
    }
    if (dis[x] < l && dis[y] < l) {
      if (dis[x]+dis[y]+w==2*l) {
        ++ans;
      } else if(dis[x]+dis[y]+w>2*l) {
        ans+=2;
      }
    }
  }
  wt(ans);
}

int main(int argc, char **argv) {
#ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
#endif
  int T = 1;
  // rd(T);
  while (T--) {
    solve();
  }
  return 0;
}