Submission #1106744

#TimeUsernameProblemLanguageResultExecution timeMemory
1106744fryingducHotspot (NOI17_hotspot)C++17
100 / 100
571 ms1360 KiB
#include "bits/stdc++.h" using namespace std; #ifdef duc_debug #include "bits/debug.h" #else #define debug(...) #endif const int maxn = 5005; int n, m, k; vector<int> g[maxn]; int d[maxn], rev_d[maxn]; long long cnt[maxn], rev_cnt[maxn]; long double f[maxn]; void bfs(int src, int d[], long long cnt[]) { for(int i = 1; i <= n; ++i) { d[i] = 1e9; cnt[i] = 0; } queue<int> q; q.push(src); d[src] = 0, cnt[src] = 1; while(!q.empty()) { int u = q.front(); q.pop(); for(auto v:g[u]) { if(d[v] > d[u] + 1) { d[v] = d[u] + 1; cnt[v] = cnt[u]; q.push(v); } else if(d[v] == d[u] + 1) { cnt[v] += cnt[u]; } } } } void solve() { cin >> n >> m; for(int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; ++u, ++v; g[u].push_back(v); g[v].push_back(u); } int q; cin >> q; while(q--) { int u, v; cin >> u >> v; ++u, ++v; bfs(u, d, cnt); bfs(v, rev_d, rev_cnt); for(int i = 1; i <= n; ++i) { if(d[i] + rev_d[i] == d[v]) { f[i] += (1.0 * cnt[i] * rev_cnt[i]) / cnt[v]; } } } int res = 0; for(int i = 1; i <= n; ++i) { if(res == 0 || f[res] < f[i]) res = i; } cout << res - 1; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); 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...