제출 #1160991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160991		hijackedsoul	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	12 ms	23884 KiB

Main

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

std::vector <vector<pair<int, int>>> adj(500005);
std::vector <vector<int>> dist(2, vector <int> (500005, LLONG_MAX/2));
std::vector <bool> vis_s(500005, false), vis_t(500005, false);

//nvm dijkstra cannot dfs this
void dijk_s(int idx, int source) {
    using T = pair<long long, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    dist[idx][source] = 0;
    pq.push({0, source});
    
    while (!pq.empty()) {
        const auto [cdist, cur] = pq.top(); // 'cur' is the current node
        pq.pop();
        if (cdist != dist[idx][cur]) { continue; }
        for (auto &edge : adj[cur]) {
            int next = edge.first;
            int weight = edge.second;
            if (cdist + weight < dist[idx][next]) {
                dist[idx][next] = cdist + weight;
                pq.push({dist[idx][next], next});
            }
        }
    }
}




int32_t main(){
	int n, m, s, t, l, k;
	std::cin >> n >> m >> s >> t >> l >> k;
	
	for(int i=0; i<m; i++){
		int a, b, c;
		std::cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	//dfs from s then dfs from t
	//just put in array and upper bound or smth to query how much can
	
	dijk_s(0, s);
	dijk_s(1, t);
	std::vector <int> dist_s, dist_t;
	for(int i=1; i<=n; i++){
		dist_s.push_back(dist[0][i]);
		dist_t.push_back(dist[1][i]);
		//std::cout << dist[0][i] << " ";
	}
	sort(dist_s.begin(), dist_s.end());
	sort(dist_t.begin(), dist_t.end());
	int ans=0;
	for(int i=0; i<n; i++){
		int t=k-l-dist_s[i];//dist_t gotta be <=t to make it
		int ind=upper_bound(dist_t.begin(), dist_t.end(), t)-dist_t.begin();
		//std::cout << ind << " ";
		ans+=ind;
	}
	std::cout << ans;
}

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