Submission #1248717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248717		Bui_Quoc_Cuong	Construction Project 2 (JOI24_ho_t2)	C++20	45 / 100	2095 ms	24768 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

int numNode, numEdge, sour, fin, bonusLen;
long long targetLen;

vector <array <int, 2>> G[N];

int maxWei = 0;

void init(){
	cin >> numNode >> numEdge >> sour >> fin >> bonusLen >> targetLen;
	for(int i = 1; i <= numEdge; i++){
		int u, v, w; cin >> u >> v >> w;
		G[u].push_back({v, w}); G[v].push_back({u, w});
		maxWei = max(w, maxWei);
	}
	maxWei = max(maxWei, bonusLen);
	maxWei *= 2;
}

namespace sub1{
	long long dist1[N], dist2[N];

	void dijk(int sour, long long dist[]){
		#define bg array <long long, 2>
		priority_queue <bg, vector <bg>, greater <bg>> pq;
		for(int i = 1; i <= numNode; i++){
			dist[i] = 1e18;
		}
		pq.push({dist[sour] = 0, sour});

		while(!pq.empty()){
			long long cost = pq.top()[0];
			int u = pq.top()[1];
			pq.pop();
			if(cost > dist[u]) continue;
			for(const array <int, 2> it : G[u]){
				int v = it[0], w = it[1];
				if(dist[v] > cost + w){
					dist[v] = cost + w;
					pq.push({dist[v], v});
				}
			}
		}
	}

	void solve(){
		dijk(sour, dist1); dijk(fin, dist2);
		bool check = dist1[fin] <= targetLen;
		if(check){
			cout << 1LL * numNode * (numNode - 1) / 2;
			return;
		}		
		int ans = 0;
		for(int u = 1; u <= numNode; u++){
			for(int v = u + 1; v <= numNode; v++){
				if(dist1[u] + bonusLen + dist2[v] <= targetLen){
					ans++;
				} 
				if(dist1[v] + bonusLen + dist2[u] <= targetLen){
					ans++;
				}
			}	
		}
		cout << ans;
	}
}

namespace sub2{


	void solve(){

	}
}

void process(){
	return sub1::solve();	
	return sub2::solve();
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);   
    #define taskname "kieuoanh"
    if(fopen(taskname".inp", "r")){ 
        freopen(taskname".inp", "r", stdin); 
        freopen(taskname".out", "w", stdout);
    }
    init();
    process();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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