제출 #1324803

#제출 시각아이디문제언어결과실행 시간메모리
1324803Zone_zoneeConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
4 ms3640 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+10;

vector<pair<int, ll>> adj[N];
ll dist1[N], dist2[N];
void dijkstra(int st, ll *dist){
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({dist[st] = 0, st});
    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(dist[u] < d) continue;
        for(auto [v, w] : adj[u]){
            if(dist[v] > d+w){
                pq.push({dist[v] = d+w, v});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, st, en, l, k;
    cin >> n >> m >> st >> en >> l >> k;
    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    memset(dist1, 0x3f, sizeof dist1);
    memset(dist2, 0x3f, sizeof dist2);
    dijkstra(st, dist1);
    dijkstra(en, dist2);
    vector<ll> v;
    for(int i = 1; i <= n; ++i) v.push_back(dist2[i]);
    sort(v.begin(), v.end());
    //(st -> u) + l + (v -> en) <= k
    //(v -> en) <= k - l - (st -> u)
    ll res = 0;
    for(int i = 1; i <= n; ++i){
        // cerr << "dbg : " << dist1[i] << '\n';
        // cerr << "dbg : " << upper_bound(v.begin(), v.end(), k - l - dist1[i]) - v.begin() << '\n';
        res += upper_bound(v.begin(), v.end(), k - l - dist1[i]) - v.begin();
        if(dist2[i] <= k - l - dist1[i]) res--;
    }
    cout << res << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...