Submission #1201047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201047		akuyga	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	229 ms	24396 KiB

Main

#include<bits/stdc++.h>
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define int long long
using namespace std;
int32_t main(){
    int N,M;
    cin>>N>>M;
    vector<ii> A[N+1];
    int S,T,L,K;
    cin>>S>>T>>L>>K;
    while(M--){
        int x,y,z;
        cin>>x>>y>>z;
        A[x].push_back(mp(z,y));
        A[y].push_back(mp(z,x));
    }
    vector<int> dist1(N+1,LLONG_MAX);
    priority_queue<ii,vector<ii>,greater<ii>> PQ;
    dist1[S]=0;
    PQ.push(mp(0,S));
    while(!PQ.empty()){
        int node=PQ.top().s;
        int d=PQ.top().f;
        PQ.pop();
        if(dist1[node]!=d)continue;
        for(auto i:A[node])
            if(dist1[i.s]>d+i.f){
                dist1[i.s]=d+i.f;
                PQ.push(mp(d+i.f,i.s));
            }
    }
    if(dist1[T]<=K){cout<<(N*(N-1))/2; return 0;}
    vector<int> dist2(N+1,LLONG_MAX);
    dist2[T]=0;
    PQ.push(mp(0,T));
    while(!PQ.empty()){
        int node=PQ.top().s;
        int d=PQ.top().f;
        PQ.pop();
        if(dist2[node]!=d)continue;
        for(auto i:A[node])
            if(dist2[i.s]>d+i.f){
                dist2[i.s]=d+i.f;
                PQ.push(mp(d+i.f,i.s));
            }
    }
    vector<int> V;
    for(int i=1;i<=N;i++){
        if(dist2[i]!=LLONG_MAX)V.push_back(dist2[i]);
    }
    sort(V.begin(),V.end());
    int c=0;
    for(int i=1;i<=N;i++){
        if(dist1[i]==LLONG_MAX)continue;
        int quota=K-dist1[i]-L;
        auto itr=upper_bound(V.begin(),V.end(),quota);
        c+=itr-V.begin();
    }
    cout<<c;
}

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