제출 #1363603

#제출 시각아이디문제언어결과실행 시간메모리
1363603inesfiConstruction Project 2 (JOI24_ho_t2)C++20
100 / 100
156 ms24904 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"

const int TAILLEMAXI=200*1000+2, INFINI=1e18;
vector<pair<int,int>> adja[TAILLEMAXI];
int dist[TAILLEMAXI][2];
int n, m, depart, arrive, temps_ajout, temps_total;

void dijkstra(int deb, int tab){
    priority_queue<pair<int,int>> en_cours;
    en_cours.push({0, deb});
    while (!en_cours.empty()){
        int d = -en_cours.top().first;
        int a = en_cours.top().second;
        en_cours.pop();
        if (dist[a][tab]==INFINI){
            dist[a][tab]=d;
            for (auto v:adja[a]){
                if (dist[v.first][tab]==INFINI){
                    en_cours.push({-(d+v.second), v.first});
                }
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>depart>>arrive>>temps_ajout>>temps_total;
    for (int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adja[a].push_back({b,c});
        adja[b].push_back({a,c});
    }
    for (int i=1;i<=n;i++){
        dist[i][0]=INFINI;
        dist[i][1]=INFINI;
    }
    dijkstra(depart, 0);
    dijkstra(arrive, 1);
    int rep=0;
    if (dist[arrive][0]<=temps_total){
        rep=(n*(n-1))/2;
        cout<<rep<<endl;
        return 0;
    }
    vector<int> dist_depart, dist_arrivee;
    for (int i=1;i<=n;i++){
        dist_depart.push_back(dist[i][0]);
        dist_arrivee.push_back(dist[i][1]);
    }
    sort(dist_depart.begin(), dist_depart.end());
    sort(dist_arrivee.begin(), dist_arrivee.end());
    int compt_arrivee=n-1;
    for (int i=0;i<n;i++){
        while (compt_arrivee>=0 and dist_depart[i]+temps_ajout+dist_arrivee[compt_arrivee]>temps_total){
            compt_arrivee--;
        }
        //cout<<compt_arrivee<<endl;
        rep+=compt_arrivee+1;
    }
    cout<<rep<<endl;
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…