Submission #1298978

#TimeUsernameProblemLanguageResultExecution timeMemory
1298978MasterMoonConstruction Project 2 (JOI24_ho_t2)C++20
100 / 100
264 ms24748 KiB
#include <bits/stdc++.h>
using namespace std;
#define __Master_Moon__ int main()
#define ll long long
#define el "\n"
#define base 300
#define fi first
#define sq(x) (x)*(x) 
#define se second   
#define pub push_back  
#define puf push_front
#define pii pair <int, int>
#define pll pair <long long, long long>
#define piii pair <long long, pair <int, int>> 
#define iiii pair <int, pair <int, pair <int, int>>>
#define plll pair <long long, pair <long long, long long>>
#define FOR(i, a, b) for(int i = (a);i <=(b);i++)
#define FO(i, a, b) for(int i = (a);i >= (b);i--)
#define REP(i, n) for(int i = 0;i < (n);i++)
long const maxn = 2e5 + 50;
ll n,m,s,ed,l,k,ans;
ll d[maxn][2]; 
vector<pll> g[maxn];
vector<ll> val;
void dist(ll star,ll t)
{
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    pq.push({0,star});
    d[star][t] = 0;
    while(pq.size())
    {
        ll u = pq.top().se;
        ll du = pq.top().fi;
        pq.pop();
        if(du != d[u][t]) continue;
        for(pii x : g[u])
        {
            if(du + x.se < d[x.fi][t])
            {
                d[x.fi][t] = du + x.se;
                pq.push({d[x.fi][t],x.fi}); 
            }
        }
    }
}
void solve() 
{
    cin >> n >> m >> s >> ed >> l >> k;
    FOR(i,1,m)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pub({v,w});
        g[v].pub({u,w});
    }
    memset(d,0x3f,sizeof d);
    dist(s,0);
    dist(ed,1);
    if(d[ed][0] <= k)
    {
        cout << n*(n-1)/2;
        return;
    }
    FOR(i,1,n) val.pub(d[i][1]);
    sort(val.begin(),val.end());
    FOR(i,1,n)
    {
        ll mtp = k - l - d[i][0];
        int tmp = upper_bound(val.begin(),val.end(),mtp) - val.begin();
        ans += tmp; 
    }   
    cout << ans;    
} 
__Master_Moon__
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    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...