Submission #1326826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326826		wangzhiyi33	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	142 ms	24244 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair<int,int> 
#define fir first
#define sec second

const int maxn=2e5;
int n,m,s,t,l,k;
vector<ii>adj[maxn+2];
int bia[maxn+2],blk[maxn+2];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>s>>t>>l>>k;
    for(int q=1;q<=m;q++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    for(int q=1;q<=n;q++){
        bia[q]=blk[q]=1e18;
    }

    priority_queue<ii,vector<ii>,greater<ii> >pq;
    pq.push({0,s}); bia[s]=0;
    while(pq.size()){
        ii cur=pq.top(); pq.pop();
        if(cur.fir!=bia[cur.sec])continue;
        for(auto [v,w] : adj[cur.sec]){
            if(bia[v]>cur.fir+w){
                bia[v]=cur.fir+w;
                pq.push({bia[v],v});
            }
        }
    }

    pq.push({0,t}); blk[t]=0;
    while(pq.size()){
        ii cur=pq.top(); pq.pop();
        if(cur.fir!=blk[cur.sec])continue;
        for(auto [v,w] : adj[cur.sec]){
            if(blk[v]>cur.fir+w){
                blk[v]=cur.fir+w;
                pq.push({blk[v],v});
            }
        }
    }
    
    if(bia[t]<=k){
        cout<<n*(n-1)/2<<endl;
        return 0;
    }

    vector<int>cek;
    for(int q=1;q<=n;q++){
        cek.push_back(blk[q]);
    }
    sort(cek.begin(),cek.end());

    int ans=0;
    for(int q=1;q<=n;q++){
        int sisa=k-l-bia[q];
        int idx=upper_bound(cek.begin(),cek.end(),sisa)-cek.begin();
        ans+=idx;
    }
    cout<<ans<<endl;
}

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