Submission #1112283

#TimeUsernameProblemLanguageResultExecution timeMemory
1112283Zero_OPConstruction Project 2 (JOI24_ho_t2)C++14
45 / 100
2094 ms20168 KiB
#include <bits/stdc++.h> using namespace std; const long long inf = 1e18; void testcase(){ int N, M, S, T, L; long long K; cin >> N >> M >> S >> T >> L >> K; --S, --T; vector<vector<pair<int, int>>> adj(N); while(M--){ int u, v, w; cin >> u >> v >> w; --u, --v; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } auto dijkstra = [&](int s){ vector<long long> d(N, inf); d[s] = 0; using node = pair<long long, int>; priority_queue<node, vector<node>, greater<node>> pq; pq.push({d[s], s}); while(!pq.empty()){ long long cur; int u; tie(cur, u) = pq.top(); pq.pop(); for(auto [v, w] : adj[u]){ if(d[v] > d[u] + w){ d[v] = d[u] + w; pq.push({d[v], v}); } } } return d; }; vector<long long> dS = dijkstra(S), dT = dijkstra(T); if(dS[T] <= K){ cout << 1LL * N * (N - 1) / 2; return; } int cnt = 0; for(int i = 0; i < N; ++i){ for(int j = i + 1; j < N; ++j){ long long cur = min(dS[i] + dT[j], dS[j] + dT[i]) + L; if(cur <= K) ++cnt; } } cout << cnt << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int T = 1; // cin >> T; while(T--) testcase(); return 0; }

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:32:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |             for(auto [v, w] : adj[u]){
      |                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...