제출 #1337350

#제출 시각아이디문제언어결과실행 시간메모리
1337350hyyhConstruction Project 2 (JOI24_ho_t2)C++20
53 / 100
2094 ms24256 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <tuple>
#include <math.h>
#include <cstring>
#include <bitset>
#include <set>
#include <map>

#define int long long

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;

#define endl '\n'
#define f first
#define s second
#define all(x) begin(x),end(x)

int const N = 2e5+10;

vector<pii> adj[N];
int walk1[N];
int walk2[N];

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(walk1,-1,sizeof walk1);
    memset(walk2,-1,sizeof walk2);
    int n;cin >> n;
    int m;cin >> m;
    int st,ed;cin >> st >> ed;
    int l,k;cin >> l >> k;
    for(int i{};i < m;i++){
        int a,b,c;cin >> a >> b >> c;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.emplace(0,st);
    walk1[st] = 0;
    while(!pq.empty()){
        auto [weight,pos] = pq.top();pq.pop();
        if(weight < walk1[pos]) continue;
        for(auto [k,cost]:adj[pos]){
            if(walk1[k] == -1 || weight+cost < walk1[k]){
                walk1[k] = weight+cost;
                pq.emplace(weight+cost,k);
            }
        }
    }
    pq.emplace(0,ed);
    walk2[ed] = 0;
    while(!pq.empty()){
        auto [weight,pos] = pq.top();pq.pop();
        if(weight < walk2[pos]) continue;
        for(auto [k,cost]:adj[pos]){
            if(walk2[k] == -1 || weight+cost < walk2[k]){
                walk2[k] = weight+cost;
                pq.emplace(weight+cost,k);
            }
        }
    }
    // for(int i{1};i <= n;i++){
    //     cout << walk1[i] << " " << walk2[i] << endl;
    // }
    if(walk1[ed] != -1 && walk1[ed] <= k){
        cout << (1LL*n*(n-1))/2;
        return 0;
    }
    vector<int> vc;
    for(int i{1};i <= n;i++){
        if(walk2[i] == -1) continue;
        vc.emplace_back(walk2[i]);
    }
    sort(all(vc));
    // for(auto k:vc) cout << k << " ";
    // cout << endl;
    ll ans = 0;
    for(int i{1};i <= n;i++){
        if(walk1[i] == -1) continue;
        auto it = upper_bound(all(vc),k-walk1[i]-l);
        //cout << i << " " << walk1[i] << " " << it-vc.begin() << endl;
        //if(it == vc.end()) continue;
        ans += (it-vc.begin());
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...