Submission #1131190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131190		Newtonabc	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	6 ms	5464 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<pair<long long,int>> adj[N];
long long dst[N],ded[N];
bool vs[N];
int n;
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> q;
void dijkstra(int u,long long *dist){
    for(int i=1;i<=n;i++) vs[i]=false,dist[i]=LLONG_MAX;
    dist[u]=0;
    q.push({0,u});
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vs[u]) continue;
        vs[u]=true;
        for(pair<long long,int> tmp:adj[u]){
            long long w=tmp.first;
            int v=tmp.second;
            if(dist[u]+w<dist[v]){
                dist[v]=dist[u]+w;
                q.push({dist[v],v});
            }
        }
    }
}
int main(){
    int m,s,t;
    long long l,k;
    cin>>n >>m >>s >>t >>l >>k;
    for(int i=0;i<m;i++){
        int u,v;
        long long w;
        cin>>u >>v >>w;
        adj[u].push_back({w,v});
        adj[v].push_back({w,u});
    }
    dijkstra(s,dst);
    dijkstra(t,ded);
    if(l>k && dst[t]>k){
        cout<<0;
        return 0;
    }
    sort(ded+1,ded+n+1);
    long long ans=0;
    for(int i=1;i<=n;i++){
        long long sch=k-l-dst[i];
        long long tmp=upper_bound(ded+1,ded+n+1,sch)-ded;
        ans+=tmp-1;
    }
    cout<<ans;
}

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