제출 #1148653

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

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

const int maxn=2e5;
vector<pll> adj[maxn+1];

void solve() {
    ll n,m,s,t,l,k;
    cin>>n>>m>>s>>t>>l>>k;
    while(m--){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    ll d1[n+1],d2[n+1];
    memset(d1,63,sizeof(d1));
    memset(d2,63,sizeof(d2));
    priority_queue<pll> pq;
    bool vis[n+1];
    memset(vis,0,sizeof(vis));
    d1[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        int v=pq.top().sc;
        pq.pop();
        if(vis[v])continue;
        vis[v]=1;
        for(auto[u,w]:adj[v])if(!vis[u]){
            d1[u]=min(d1[u],d1[v]+w);
            pq.push({-d1[u],u});
        }
    }
    if(d1[t]<=k){
        cout<<n*(n-1)/2<<'\n';
        return;
    }
    memset(vis,0,sizeof(vis));
    d2[t]=0;
    pq.push({0,t});
    while(!pq.empty()){
        int v=pq.top().sc;
        pq.pop();
        if(vis[v])continue;
        vis[v]=1;
        for(auto[u,w]:adj[v])if(!vis[u]){
            d2[u]=min(d2[u],d2[v]+w);
            pq.push({-d2[u],u});
        }
    }
    sort(d2+1,d2+n+1);
    ll c=0;
    for(int i=1;i<=n;i++){
        c+=upper_bound(d2+1,d2+n+1,k-l-d1[i])-d2-1;
    }
    cout<<c<<'\n';
}

int main() {
    #ifdef FPO
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

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