Submission #1318763

#TimeUsernameProblemLanguageResultExecution timeMemory
1318763b_esma101811Odašiljači (COCI20_odasiljaci)C++20
7 / 70
32 ms32964 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAX = 1e3 + 10; const double INF = 1e18; vector<pair<int, double>> adj[MAX]; vector<int> vis(MAX, 0); vector<double> dis(MAX, INF); void dij(int k) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; q.push({0, k}); dis[k] = 0; while(q.size()) { auto [x, u] = q.top(); q.pop(); if(vis[u]) continue; vis[u] = 1; for(auto [v, len] : adj[u]) { if(!vis[v] && dis[u] + len < dis[v]) { dis[v] = dis[u] + len; q.push({dis[v], v}); } } } } void solve() { vector<int> vt; int n; cin >> n; double a[n + 1]; double b[n + 1]; for(int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } if(n == 1) { cout << 0.0000000 << endl; return; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i != j) { adj[i].push_back({j, sqrt((abs(a[i] - a[j]) / 2) * (abs(a[i] - a[j]) / 2) + (abs(b[i] - b[j]) / 2) * (abs(b[j] - b[i]) / 2))}); adj[j].push_back({i, sqrt((abs(a[i] - a[j]) / 2) * (abs(a[i] - a[j]) / 2) + (abs(b[i] - b[j]) / 2) * (abs(b[j] - b[i]) / 2))}); } } } for(int i = 1; i <= n; i++) { if(!vis[i]) { dij(i); } } double ans = 0; for(int i = 1; i <= n; i++) { ans = max(ans, dis[i]); } cout << setprecision(7) << fixed << ans << endl; } signed main(){ int t = 1; //cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...