Submission #1095702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095702		vjudge1	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	161 ms	24756 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=2e5+5;
const ll inf=2e18;
int n,m,s,t,l;
ll k;
struct duongdi
{
    int u;
    ll w;
    bool operator < (const duongdi &o)const
    {
        return w>o.w;
    }
};
ll d[2][maxN+1];
vector<duongdi> adj[maxN+1];
priority_queue<duongdi> pq;
void dijkstra(int s,int type)
{
    for(int i=1;i<=n;i++)
    {
        d[type][i]=inf;
    }
    d[type][s]=0;
    pq.push({s,0});
    while(!pq.empty())
    {
        duongdi tmp=pq.top();
        pq.pop();
        int u=tmp.u;
        ll w=tmp.w;
        if(d[type][u]<w)
        {
            continue;
        }
        for(auto [v,nw]:adj[u])
        {
            if(d[type][v]>d[type][u]+nw)
            {
                d[type][v]=d[type][u]+nw;
                pq.push({v,d[type][v]});
            }
        }
    }
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s>>t>>l>>k;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dijkstra(s,0);
    dijkstra(t,1);
    if(d[0][t]<=k)
    {
        cout<<1LL*n*(n-1)/2;
        return 0;
    }
    sort(d[0]+1,d[0]+n+1);
    sort(d[1]+1,d[1]+n+1);
    ll ans=0;
    for(int i=1,j=n;i<=n;i++)
    {
        while(j>0&&d[0][i]+d[1][j]+l>k)
        {
            j--;
        }
        ans+=j;
    }
    cout<<ans;
}

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