제출 #1341252

#제출 시각아이디문제언어결과실행 시간메모리
1341252vtnooConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
120 ms20480 KiB
#include <bits/stdc++.h>
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define pb push_back
using namespace std;
typedef long long ll;

using ii=pair<ll,ll>;

const int N=2e5+5;
const ll INF=1e18+5;
vector<ii>adj[N];
int n;

ll gauss(ll n){
    return (n*(n-1))/2;
}

vector<ll>distances(ll s){
    vector<ll>dist(n+1,INF),parent(n+1);
    priority_queue<ii,vector<ii>,greater<ii>>q;
    q.push({0,s});
    dist[s]=0;
    while(sz(q)){
        auto [d,u]=q.top();q.pop();
        if(d!=dist[u])continue;
        for(auto [v,c]:adj[u]){ 
            if(dist[v]>dist[u]+c){
                dist[v]=dist[u]+c;
                parent[v]=u;
                q.push({dist[v],v});
            }
        }
    }
    return dist;
}

int main(){
    ll m;cin>>n>>m;
    ll s,t,l,k;cin>>s>>t>>l>>k;
    L(i,0,m-1){
        ll a,b,c;cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    auto ds=distances(s),dt=distances(t);
    if(ds[t]<=k){
        cout<<gauss(n)<<endl;
        return 0;
    }
    vector<ll>nodes;
    L(i,1,n){
        nodes.pb(dt[i]);
    }
    sort(all(nodes));
    ll ans=0;
    L(i,0,n-1){
        if(k<ds[i])continue;
        ll ll=-1,rr=sz(nodes);
        while(rr-ll>1){
            int mm=(rr+ll)/2;
            if(ds[i]+l+nodes[mm]<=k){
                ll=mm;
            }else{
                rr=mm;
            }
        }
        ans+=ll+1;
    }
    cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...