제출 #1341163

#제출 시각아이디문제언어결과실행 시간메모리
1341163joacruConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
1 ms344 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define forn(i,n) for(int i=0;i<(int)n;++i)

#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

using namespace __gnu_pbds;

template<typename T>
using iset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;

const int MAXN = 200005;
const ll INF = 1000000000000000000;

int n;
vector<pair<int,int>> g[MAXN];

vector<ll> dijkstra(int s){
    vector<ll> dist(n, INF);
    dist[s] = 0;
    priority_queue<pair<ll,int>> pq;
    pq.push({0,s});
    while(SZ(pq)){
        int u = pq.top().second;
        ll d = -pq.top().first;
        pq.pop();
        if(dist[u] != d) continue;
        for(auto [v, w]: g[u]){
            ll nd = d + w;
            if(nd < dist[v]){
                dist[v] = nd;
                pq.push({-nd, v});
            }
        }
    }
    return dist;
}

struct P{
    ll a, b;
    int i;
    bool operator<(const P&o)const{
        return a-b<o.a-o.b;
    }
};

int main(){

    cin.tie(0);
    ios::sync_with_stdio(0);

    int m, s, t, l;
    ll k;

    cin>>n>>m>>s>>t>>l>>k;
    --s, --t;

    while(m--){
        int u, v, w;
        cin>>u>>v>>w;
        --u, --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    auto fromS = dijkstra(s);
    auto fromT = dijkstra(t);

    /*forn(i,n) cerr<<fromS[i]<<" ";
    cerr<<endl;
    forn(i,n) cerr<<fromT[i]<<" ";
    cerr<<endl;*/

    vector<P> ps(n);
    forn(i,n) ps[i] = {fromS[i],fromT[i],i};

    sort(ALL(ps));

    iset<pair<ll,int>> pre;
    ll ans = 0;
    forn(i,n){
        ll aux = k - ps[i].b - l;
        ans += pre.order_of_key({aux,-1});
        pre.insert({ps[i].a,i});
    }

    cout<<ans<<"\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...