Submission #1248715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248715		Bui_Quoc_Cuong	Construction Project 2 (JOI24_ho_t2)	C++20	16 / 100	2094 ms	12388 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 dist[N];

	bool check(){
		#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});
				}
			}
		}

		return dist[fin] <= targetLen;
	}

	void solve(){
		int ans = 0;
		for(int u = 1; u <= numNode; u++){
			for(int v = u + 1; v <= numNode; v++){
				G[u].push_back({v, bonusLen}); G[v].push_back({u, bonusLen});
				if(check()) {
					ans++;
				}
				G[u].pop_back(); G[v].pop_back();
			}
		}
		cout << ans;
	}
}

void process(){
	return sub1::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:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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