Submission #1182685

#TimeUsernameProblemLanguageResultExecution timeMemory
1182685DedibeatConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
8 ms5192 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define F first #define S second #define all(x) (x).begin(), (x).end() #define int long long int N, M, S, T, L, K; using node = pair<ll, ll>; vector<node> adj[200005]; signed main() { ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin >> N >> M >> S >> T >> L >> K; for(int i = 0; i < M; i++) { int u, v, w; cin >> u >> v >> w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } auto dij = [&](int s) { priority_queue<node, vector<node> , greater<node>> q; vector<ll> d(N + 5, 1e17); d[s] = 0; q.emplace(0, s); while(!q.empty()) { auto [c, v] = q.top(); q.pop(); if(c != d[v]) continue; for(auto [u, w] : adj[v]) { if(c + w < d[u]) { d[u] = c + w; q.emplace(c + w, u); } } } return d; }; auto ds = dij(S); auto dt = dij(T); // print(ds); // print(dt); ll cnt = 0; for(int i = 1; i <= N; i++) { for(int j = i + 1; j <= N; j++) { ll cost = min(ds[i] + dt[j], ds[j] + dt[i]) + L; if(cost <= K) { cnt++; // cout << cost << endl; // cout << i << " ," << j << endl; } } } cout << cnt << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...