제출 #1163147

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

Main

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

vector<pair<ll, int>> adj[200005];
int v1[200005];
int v2[200005];
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(NULL);
    ll N,M,S,T;
    ll L,K;
    cin>>N>>M>>S>>T>>L>>K;
    S--;T--;
    ll d1[N];
    ll d2[N];
    for (int i=0;i<N;i++) {
        d1[i] = LLONG_MAX/2;
        d2[i] = LLONG_MAX/2;
    }
    for (int i=0;i<M;i++) {
        int i1,i2;
        ll i3;
        cin>>i1>>i2>>i3;
        i1--;i2--;
        adj[i1].push_back(make_pair(i3,i2));
        adj[i2].push_back(make_pair(i3,i1));
    }
    d1[S] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll, int>>, greater<pair<ll,int>>> pq;
    pq.push(make_pair(0,S));
    while (!pq.empty()) {
        ll l = pq.top().first;
        ll u = pq.top().second;
        pq.pop();
        if (v1[u]) {continue;}
        v1[u]=1;
        for (auto pp:adj[u]) {
            if (d1[pp.second]>d1[u]+pp.first) {
                d1[pp.second] = d1[u]+pp.first;
                pq.push(make_pair(d1[u]+pp.first, pp.second));
            }
        }
    }
    pq.push(make_pair(0,T));
    d2[T] = 0;
    while (!pq.empty()) {
        ll l = pq.top().first;
        ll u = pq.top().second;
        pq.pop();
        if (v2[u]) {continue;}
        v2[u]=1;
        for (auto pp:adj[u]) {
            if (d2[pp.second]>d2[u]+pp.first) {
                d2[pp.second] = d2[u]+pp.first;
                pq.push(make_pair(d2[u]+pp.first, pp.second));
            }
        }
    }
    sort(d2, d2+N);
    ll ans=0;
    if (d1[T]<=K) {
        cout << (N*(N-1))/2LL;
        return 0;
    }
    for (int i=0;i<N;i++) {
        ans+=max(upper_bound(d2,d2+N, K-L-d1[i])-d2, 0L);
    }
    cout << ans;
    return 0;
}
/*
6 4
2 5 10 1
1 2 10
2 3 10
2 4 10
5 6 10
*/

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