Submission #1170745

#TimeUsernameProblemLanguageResultExecution timeMemory
1170745akqxolotlConstruction Project 2 (JOI24_ho_t2)C++20
100 / 100
154 ms24644 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define debug(x) cerr<<#x<<" is "<<x<<endl; #define fi first #define se second typedef pair<int,int> pii; #define pb push_back bool svis[200005]; int sdis[200005]; bool tvis[200005]; int tdis[200005]; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,m;cin>>n>>m; int s,t,l,k;cin>>s>>t>>l>>k; vector<pair<int,int>> adj[n+1]; for(int i=0;i<m;i++){ int x,y,w;cin>>x>>y>>w; adj[x].pb({y,w}); adj[y].pb({x,w}); } for(int i=0;i<=n;i++){ tdis[i]=LLONG_MAX; sdis[i]=LLONG_MAX; } priority_queue<pii,vector<pii>,greater<pii>> pq; pq.push({0,s}); while(!pq.empty()){ int cd=pq.top().fi; int cn=pq.top().se; pq.pop(); if(svis[cn])continue; svis[cn]=1; sdis[cn]=cd; for(pii p:adj[cn]){ if(svis[p.fi])continue; pq.push({p.se+cd,p.fi}); } } pq.push({0,t}); while(!pq.empty()){ int cd=pq.top().fi; int cn=pq.top().se; pq.pop(); if(tvis[cn])continue; tvis[cn]=1; tdis[cn]=cd; for(pii p:adj[cn]){ if(tvis[p.fi])continue; pq.push({p.se+cd,p.fi}); } } if(tdis[s]<=k){ cout<<(n-1)*n/2<<'\n'; return 0; } vector<int> ss; for(int i=1;i<=n;i++){ //debug(tdis[i]) ss.pb(tdis[i]); } sort(ss.begin(),ss.end()); //for(auto i:ss)debug(i) //for(int i=0;i<n;i++)debug(tdis[i]) int ans=0; for(int i=1;i<=n;i++){ int temp=(upper_bound(ss.begin(),ss.end(),(k-l-sdis[i]))-ss.begin()); if(sdis[i]==LLONG_MAX)continue; //debug(sdis[i]) //debug(temp) ans+=temp; } cout<<ans<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...