Submission #1164183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164183		dolphy	Construction Project 2 (JOI24_ho_t2)	C++20	8 / 100	2095 ms	23724 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb(a) push_back(a)
#define pp pop_back
#define mp(a, b) make_pair(a, b)
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, s, t, l, k;
    cin >> n >> m >> s >> t >> l >> k;
    vector <pair <int, int> > adj[n+1];
    int a, b, c;
    for (int i=0; i<m; i++) {
        cin >> a >> b >> c;
        adj[a].pb(mp(c, b));
        adj[b].pb(mp(c, a));
    }
    priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
    int x[n+1], y[n+1];
    for (int i=1; i<=n; i++) {x[i]=LLONG_MAX; y[i]=LLONG_MAX;}
    x[s]=0;
    pq.push(mp(0, s));
    while (!pq.empty()) {
        pair <int, int> p=pq.top();
        pq.pop();
        if (p.first!=x[p.second]) continue;
        for (auto i:adj[p.second]) {
            if (x[i.second]>x[p.second]+i.first) {
                x[i.second]=x[p.second]+i.first;  
                pq.push(mp(x[i.second], i.second));          
            }
        }
    }
    if (x[t]<=k) {cout << n*(n-1)/2 << "\n"; return 0;}
    sort(x+1, x+n+1, greater<int>());
    int tot=0, idx=1;
    y[t]=0;
    pq.push(mp(0, t));
    while (!pq.empty()) {
        pair <int, int> p=pq.top();
        if (p.first!=y[p.second]) continue;
        while (idx<=n && x[idx]>k-l-p.first) idx++;
        tot+=n+1-idx;
        pq.pop();
        for (auto i:adj[p.second]) {
            if (y[i.second]>y[p.second]+i.first) {
                y[i.second]=y[p.second]+i.first;  
                pq.push(mp(y[i.second], i.second));          
            }
        }
    }
    cout << tot << "\n";
    return 0;
}

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