제출 #1144081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144081		fryingduc	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	135 ms	23352 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, m, l;
long long k;
int s, t;
vector<pair<int, int>> g[maxn];
long long d[maxn], rev[maxn];
long long org[maxn];

void dijkstra(int src, long long d[]) {
  for(int i = 1; i <= n; ++i) {
    d[i] = 1e18;
  }
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  d[src] = 0;
  pq.push(make_pair(0, src));
  while(!pq.empty()) {
    int u = pq.top().second;
    long long dist = pq.top().first;
    pq.pop();
    if(dist > d[u]) continue;
    for(auto e:g[u]) {
      int v = e.first, w = e.second;
      if(d[v] > d[u] + w) {
        d[v] = d[u] + w;
        pq.push(make_pair(d[v], v));
      }
    }
  }
}

void solve() {
  cin >> n >> m >> s >> t >> l >> k;
  for(int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  dijkstra(s, d);
  dijkstra(t, rev);
  if(d[t] <= k) {
    cout << 1ll * n * (n - 1) / 2;
    return;
  }
  for(int i = 1; i <= n; ++i) {
    org[i] = rev[i];
  }
  long long res = 0;
  sort(rev + 1, rev + n + 1);
  for(int i = 1; i <= n; ++i) {
    int x = upper_bound(rev + 1, rev + n + 1, k - l - d[i]) - rev - 1;
    res += x;
    if(d[i] + org[i] <= k - l) {
      --res;
    }
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 47 / 47