제출 #1088184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1088184		HienTD	Construction Project 2 (JOI24_ho_t2)	C++14	100 / 100	171 ms	29436 KiB

Main

#include <bits/stdc++.h>
using namespace std;

//#define USACO

#define             fi  first
#define             se  second
#define           TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define         ALL(v)  (v).begin(), (v).end()
#define         BIT(i)  (1LL << (i))
#define     MASK(x, i)  (((x) >> (i)) & 1)
#define      REP(i, v)  for( __typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define   FOR(i, a, b)  for(int i = (a), _b = (b); i <= _b; ++ i)
#define  FORD(i, b, a)  for(int i = (b), _a = (a); i >= _a; -- i)

const string NAME = "BAITAP";

const string name = "";

const long long INF = 1e18;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int mod = 998244353;

const int mxN = 2e5 + 5;

int N, M, S, T;
long long K, L;
vector<pair<int, long long>> adj[mxN];
vector<long long> dist_from_t(mxN, INF);
vector<long long> dist_from_s(mxN, INF);

void init(void){
    cin >> N >> M;
    cin >> S >> T >> L >> K;
    FOR(i, 1, M){
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
}

void dijkstra(const int &st, const int &ty){
    if(ty == 1){
        dist_from_s[st] = 0;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        pq.push(make_pair(dist_from_s[st], st));
        while(pq.empty() == false){
            pair<long long, int> cur = pq.top();
            pq.pop();
            if(dist_from_s[cur.se] != cur.fi) continue;
            for(pair<int, long long> v : adj[cur.se]){
                if(dist_from_s[v.fi] > dist_from_s[cur.se] + v.se){
                    pq.push(make_pair(dist_from_s[v.fi] = dist_from_s[cur.se] + v.se, v.fi));
                }
            }
        }
    }
    else{
        dist_from_t[st] = 0;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        pq.push(make_pair(dist_from_t[st], st));
        while(pq.empty() == false){
            pair<long long, int> cur = pq.top();
            pq.pop();
            if(dist_from_t[cur.se] != cur.fi) continue;
            for(pair<int, long long> v : adj[cur.se]){
                if(dist_from_t[v.fi] > dist_from_t[cur.se] + v.se){
                    pq.push(make_pair(dist_from_t[v.fi] = dist_from_t[cur.se] + v.se, v.fi));
                }
            }
        }
    }
}

void process(void){
    dijkstra(S, 1);
    dijkstra(T, 2);
    if(dist_from_s[T] <= K){
        cout << 1LL * N * (N - 1) / 2;
        return;
    }
    long long ans = 0;
    sort(dist_from_t.begin() + 1, dist_from_t.begin() + 1 + N);
    FOR(i, 1, N){
        long long ok = K - L - dist_from_s[i];
        ans += lower_bound(dist_from_t.begin() + 1, dist_from_t.begin() + 1 + N, ok + 1) - (dist_from_t.begin() + 1);
    }
    cout << ans;
//    FOR(i, 1, N){
//        cerr << dist_from_s[i] << ' ' << dist_from_t[i] << '\n';
//    }
}

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    #ifdef LOCAL
        freopen((NAME + ".INP").c_str(), "r", stdin);
        freopen((NAME + ".OUT").c_str(), "w", stdout);
    #elif defined(USACO)
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    #endif

    init();
    process();
    cerr << "\nTime elapsed: " << TIME << "s.\n";
}

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