제출 #1150509

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

Main

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define     int     long long
#define     pii     pair<int,int>

const int mxN = 2e5+7 , Inf = 2e18;
int n,m , S,T,L,K , ln[2][mxN];
bool mrk[mxN];
vector<pair<int,int>> e[mxN];

void iN ()
{
    cin >> n >> m;
    cin >> S >> T >> L >> K;
    for (int i=1; i<=m; i++)
    {
        int u,v,w; cin >> u >> v >> w;
        e[u].push_back( { v , w } );
        e[v].push_back( { u , w } );
    }
    for (int i=1; i<=n; i++)
        ln[0][i] = ln[1][i] = Inf;
}

void Dijkstra (int st , int typ)
{
    memset(mrk , 0 , sizeof(mrk));
    priority_queue<pii , vector<pii> , greater<pii>> pq;
    pq.push( { 0 , st } ); ln[typ][st] = 0;
    while (!pq.empty())
    {
        auto [o , v] = pq.top();
        pq.pop();
        if (mrk[v]) continue;
        mrk[v] = true;
        for (auto [to , w] : e[v])
        {
            if (ln[typ][to] > o + w)
            {
                ln[typ][to] = o + w;
                pq.push( { o + w , to } );
            }
        }
    }
}

void ouT ()
{
    if (ln[0][T] <= K)
    {
        cout << n*(n-1)/2 << '\n';
        return;
    }
    int out = 0;
    vector<int> q;
    for (int i=1; i<=n; i++)
        q.push_back( ln[1][i] );
    sort(q.begin(),q.end());
    for (int i=1; i<=n; i++)
        out += upper_bound(q.begin(),q.end(),K-L-ln[0][i])-q.begin();
    cout << out << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);

    iN ();
    Dijkstra (S,0);
    Dijkstra (T,1);
    ouT ();
}

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