Submission #1157052

#TimeUsernameProblemLanguageResultExecution timeMemory
1157052wjliangtpeConstruction Project 2 (JOI24_ho_t2)C++20
100 / 100
137 ms23724 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,long long> > adj[200005];
long long d1[200005],d2[200005],k,ans=0;
int s,t,l,m,n,a,b,c;
#define oo 10000000000000001
priority_queue<pair<long long,int> > pq;
bitset<200005> vis;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m>>s>>t>>l>>k;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++){
        d1[i]=oo;
        d2[i]=oo;
    }
    pq.push({d1[s]=0,s});
    while(!pq.empty()){
        auto p=pq.top();
        pq.pop();
        int v=p.second;
        if(vis[v]) continue;
        vis[v]=1;
        for(auto e:adj[v]){
            int u=e.first;
            long long w=e.second;
            if(d1[u]>d1[v]+w){
                d1[u]=d1[v]+w;
                pq.push({-d1[u],u});
            }
        }
    }
    pq.push({d2[t]=0,t});
    vis.reset();
    while(!pq.empty()){
        auto p=pq.top();
        pq.pop();
        int v=p.second;
        if(vis[v]) continue;
        vis[v]=1;
        for(auto e:adj[v]){
            int u=e.first;
            long long w=e.second;
            if(d2[u]>d2[v]+w){
                d2[u]=d2[v]+w;
                pq.push({-d2[u],u});
            }
        }
    }

    if(d1[t]<=k){
        cout<<n*(n-1)/2<<'\n';
        return 0;
    }
    sort(d1+1,d1+n+1),sort(d2+1,d2+n+1);
    /*int x=1,y=n;
    while(x<=n){
        while(d1[x]+d2[y]+l>k&&y>0) y--;
        x++;
        if(y<=0) break;
        ans+=y;
    }
    */
    for(int i=1;i<=n;i++){
        ans+=upper_bound(d2+1,d2+n+1,k-l-d1[i])-(d2+1);
    }
    cout<<ans<<'\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...