Submission #1250726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250726		DangKhoizzzz	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	153 ms	24904 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e17;
const int maxn = 2e5 + 7;

int n , m , S , T , K , L;
vector <pii> g[maxn];

vector <int> dijkstra(int st)
{
    vector <int> d(n , INF);
    priority_queue <pii , vector <pii> , greater <pii>> Q;
    Q.push({0 , st});
    d[st] = 0;

    while(!Q.empty())
    {
        int c = Q.top().fi;
        int u = Q.top().se;
        Q.pop();
        if(c != d[u]) continue;

        for(pii tmp: g[u])
        {
            int v = tmp.fi;
            int w = tmp.se;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push({d[v] , v});
            }
        }
    }
    return d;
}

void solve()
{
    cin >> n >> m;
    cin >> S >> T >> L >> K;
    S--;
    T--;

    for(int i = 1; i <= m; i++)
    {
        int u , v , w; cin >> u >> v >> w;
        u--;
        v--;
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }

    vector <int> a = dijkstra(S);
    vector <int> b = dijkstra(T);

    if(a[T] <= K)
    {
        cout << n*(n-1)/2 << '\n';
        return;
    }

    sort(b.begin() , b.end());
    sort(a.begin() , a.end());

    int ans = 0;

    for(int i = 0; i < n; i++)
    {
        int j = upper_bound(b.begin() , b.end() , K - L - a[i]) - b.begin();
        ans += j;
    }
    cout << ans << '\n';
}



signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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