제출 #1161795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161795		zyq181	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	129 ms	24420 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

int dist1[200010];
int dist2[200010];
vector<pair<int, int> > adjList[200010];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
int S, T, L, K; 
int N, M;
int inp1, inp2, inp3; 

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> S >> T >> L >> K;
    for(int a=1; a<=N; a++) dist1[a] = dist2[a] = LLONG_MAX/2;
    for(int a=1; a<=M; a++) {
        cin >> inp1 >> inp2 >> inp3;
        adjList[inp1].push_back({inp3, inp2});
        adjList[inp2].push_back({inp3, inp1});
    }
    dist1[S] = 0;
    dist2[T] = 0;
    pq.push({0, S});
    while(!pq.empty()){
        int d, node;
        tie(d, node) = pq.top();
        pq.pop();
        if(d > dist1[node]) continue;
        for(auto it: adjList[node]){
            if(dist1[it.second]>dist1[node] + it.first){
                dist1[it.second] = dist1[node] + it.first;
                pq.push({dist1[it.second], it.second});
            }
        }
    }

    pq.push({0, T});
    while(!pq.empty()){
        int d, node;
        tie(d, node) = pq.top();
        pq.pop();
        if(d > dist2[node]) continue;
        for(auto it: adjList[node]){
            if(dist2[it.second]>dist2[node] + it.first){
                dist2[it.second] = dist2[node] + it.first;
                pq.push({dist2[it.second], it.second});
            }
        }
    }

    if(dist1[T] <= K){
        cout << N*(N-1)/2;
        return 0;
    }

    vector<int> v;
    for(int a=1; a<=N; a++){
        v.push_back(-dist1[a]);
    }
    sort(v.begin(), v.end());
    int ans = 0;
    for(int a=1; a<=N; a++){
        int todo = K - L - dist2[a]; //upperbound
        auto it = lower_bound(v.begin(), v.end(), -todo);
        if(it == v.end()) continue;
        ans += (v.end() - it);
    }
    cout << ans;
}

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