Submission #1138832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138832		ThylOne	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	2095 ms	21836 KiB

Main

#include<bits/stdc++.h>

#define int long long

using namespace std;

#define all(x) x.begin(), x.end()
const int maxiN = 2e5;


struct edge{
    int voisin;
    int weight;
};
struct node{
    int id;
    int weight;
};
bool operator<(node const&a, node const&b){
    return a.weight > b. weight;
}
vector<edge> links[maxiN];
int n;
const int MAX_W = 1e18;
vector<int> djistra(int source){
    vector<int> re(n, MAX_W);
    priority_queue<node> pq;
    pq.push({source, 0});
    while(!pq.empty()){
        auto act = pq.top();
        pq.pop();
        if(re[act.id] != MAX_W)continue;
        re[act.id] = act.weight;
        for(auto e:links[act.id])
            pq.push({e.voisin, e.weight+act.weight});
    }
    return re;
}
void dbg(vector<int> v){

    for(int &i:v){
        cout << i << ' ' ; 
    }
    cout<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int  m;
    cin>>n>>m;
    int D,F,len,limit;
    cin>>D>>F>>len>>limit;
    D--;
    F--;
    for(int i = 0 ;  i< m ; i++){
        int a,b,w;
        cin>>a>>b>>w;
        a--;b--;
        links[a].push_back({b, w});
        links[b].push_back({a, w});
    }
    
    vector<int> dD = djistra(D);
    vector<int> dF = djistra(F);

    vector<pair<int,int>> distId;
    for(int i = 0 ; i < n ; i++){
        distId.push_back({dF[i], i});
    }
    int ans2 = 0;
    for(int i = 0 ; i< n ; i++){
        for(int j = 0;j<n;j++){
            if(i!=j)
                if(dD[i]+len+dF[j]<=limit){
                    ans2++;}
        }
    }
    if(dD[F] <= limit){
        cout << 1LL*n*(n-1)/2<<endl;
        return 0;
    }
    sort(distId.begin(), distId.end());
    int ans = 0;
    for(int i = 0 ; i < n ; i++){
        int pos = upper_bound(all(distId),make_pair(limit-len-dD[i]+1,(long long)0)) - distId.begin();
        ans += pos;
    }
    
    cout << ans2 << endl;

}

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