제출 #1138766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138766		ThylOne	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	2 ms	4936 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;
vector<int> djistra(int source){
    vector<int> re(n, -1);
    priority_queue<node> pq;
    pq.push({source, 0});
    while(!pq.empty()){
        auto act = pq.top();
        pq.pop();
        if(re[act.id] != -1)continue;
        re[act.id] = act.weight;
        for(auto e:links[act.id])
            pq.push({e.voisin, e.weight+act.weight});
    }
    return re;
}
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(dD[i]+len+dF[j]<=limit)ans2++;
        }
    }
    cout<<ans2<<endl;/*
    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();
        if(dF[i]+dD[i]+len<=limit){pos--;}
        ans += pos+1;
    }
    cout << ans << endl;*/

}

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