제출 #1188351

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

Main

#include <bits/stdc++.h>
#define ff first
#define ss second
#define MOD 998244353
#define INF 1000000000000000009
#define ld long double
#define ll long long
#define pb push_back
using namespace std;
ll n,a,b,c,d,m,k,s,t,oldk,dst1[200007],dst2[200007],wyn;
vector<pair<ll,ll>>g[200007];//kto, ile place

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    cin>>s>>t>>c>>k;
    oldk=k;
    k-=c;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    for(int i=0;i<200007;i++){
        dst1[i]=INF;
        dst2[i]=INF;
    }
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;//koszt gdzie;
    pq.push({0,s});
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(dst1[pom.ss]!=INF)continue;
        dst1[pom.ss]=pom.ff;
        for(int i=0;i<g[pom.ss].size();i++){
            pq.push({pom.ff+g[pom.ss][i].ss,g[pom.ss][i].ff});
        }
    }
    if(dst1[t]<=oldk){
        cout<<n*(n-1)/2;
        return 0;
    }
    pq.push({0,t});
    while(pq.size()){
        auto pom=pq.top();
        pq.pop();
        if(dst2[pom.ss]!=INF)continue;
        dst2[pom.ss]=pom.ff;
        for(int i=0;i<g[pom.ss].size();i++){
            pq.push({pom.ff+g[pom.ss][i].ss,g[pom.ss][i].ff});
        }
    }
    sort(dst1,dst1+200007);
    sort(dst2,dst2+200007);
    ll p2=0;//niewziety
    for(int i=n-1;i>=0;i--){
        while(dst2[p2]+dst1[i]<=k)p2++;
        wyn+=p2;
    }
    
    cout<<wyn;
}

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