Submission #1147375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147375		koukirocks	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	140 ms	24928 KiB

Main

#include <bits/stdc++.h>
#define F first
#define S second
#define speed ios_base::sync_with_stdio(0);cin.tie(0)
#define all(x) x.begin()+1, x.end()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T>
using vvector = vector<vector<T>>;

const ll oo =0x3f3f3f3f3f3f3f3f;

void DJ(ll st,ll n,vvector<pll> &G,vector<ll> &dis) {
    vector<bool> vis(n+1);
    priority_queue<pll> Q;
    Q.push({0ll,st});
    dis[st]=0;
    while (!Q.empty()) {
        while (!Q.empty() and vis[Q.top().S]) Q.pop();
        if (Q.empty()) break;
        auto [dd,v]=Q.top();
        Q.pop();
        vis[v]=true;
        for (auto [i,w]:G[v]) {
            if (dis[i]>dis[v]+w) {
                dis[i]=dis[v]+w;
                Q.push({-dis[i],i});
            }
        }
    }
}

int main() {
    speed;
    ll n,m;
    cin>>n>>m;
    ll s,t,l,k;
    cin>>s>>t>>l>>k;
    vvector<pll> G(n+1);
    for (int i=1;i<=m;i++) {
        ll a,b,w;
        cin>>a>>b>>w;
        G[a].emplace_back(b,w);
        G[b].emplace_back(a,w);
    }
    vector<ll> d1(n+1,oo);
    DJ(s,n,G,d1);
    vector<ll> d2(n+1,oo);
    DJ(t,n,G,d2);
    if (d1[t]<=k) {
        cout<<n*(n-1)/2<<"\n";
        return 0;
    }
    ll ans=0;
    sort(all(d1));
    sort(all(d2));
    // for (int i=1;i<=n;i++) cout<<d1[i]<<" ";
    // cout<<"\n";
    // for (int i=1;i<=n;i++) cout<<d2[i]<<" ";
    // cout<<"\n";
    ll id2=n;
    for (ll i=1;i<=n;i++) {
        while (id2>=1 and d2[id2]+d1[i]+l>k) id2--;
        ans+=id2;
    }
    cout<<ans<<"\n";
    return 0;
}

/*
3 2
1 3 1 1
1 2 1
2 3 1
*/

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