Submission #1205186

#TimeUsernameProblemLanguageResultExecution timeMemory
1205186loomHotspot (NOI17_hotspot)C++20
38 / 100
101 ms14340 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define ld long double #define inf 5e18 #define nl '\n' inline void solve(){ int n, m; cin>>n>>m; vector<int> g[n]; for(int i=0; i<m; i++){ int a, b; cin>>a>>b; g[a].push_back(b); g[b].push_back(a); } int k; cin>>k; vector<pair<int,int>> v(k); for(auto &[a, b] : v) cin>>a>>b; int d[n][n], c[n][n]; for(int i=0; i<n; i++){ priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; auto &dist = d[i]; auto &cnt = c[i]; pq.push({0, i}); fill(dist, dist+n, inf); dist[i] = 0; cnt[i] = 1; while(!pq.empty()){ auto [dis, v] = pq.top(); pq.pop(); if(dis > dist[v]) continue; for(int ch : g[v]){ if(dis+1 < dist[ch]){ dist[ch] = dis+1; cnt[ch] = 1; pq.push({dist[ch], ch}); } else if(dis+1 == dist[ch]){ cnt[ch] += cnt[v]; } } } } int ans = 0; ld mx = 0; for(int i=0; i<n; i++){ ld sum = 0; for(auto [a, b] : v){ if(d[a][i] + d[i][b] == d[a][b]) sum += (c[a][i] * c[i][b])/c[a][b]; } if(sum > mx){ mx = sum; ans = i; } } cout<<ans; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int t = 1; //cin>>t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...