Submission #1182683

#TimeUsernameProblemLanguageResultExecution timeMemory
1182683DedibeatConstruction Project 2 (JOI24_ho_t2)C++20
0 / 100
9 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() template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << "(" << p.F << "," << p.S << ")"; } template<typename T> void print(const T &v, int lim = 1e9) { for(auto x : v) if(lim-- > 0) cout << x << " "; cout << "\n"; } int N, M, S, T, L, K; using node = pair<ll, ll>; vector<node> adj[200005]; int main() { 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<>> q; vector<ll> d(N + 1, 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...