Submission #587479

#TimeUsernameProblemLanguageResultExecution timeMemory
587479NekoRollyHotspot (NOI17_hotspot)C++17
100 / 100
514 ms62156 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5e3+4; const int inf = 1e9; int n,m,k; int dis[N][N],dp[N][N]; vector<int> adj[N]; bool vis[N]; double val[N]; void bfs(int rt,int dis[],int dp[]){ queue<int> d; if (vis[rt]) return; for (int i=0; i<n; i++) dis[i] = inf; dis[rt] = 0, dp[rt] = 1; for (d.push(rt); d.size(); d.pop()){ int u = d.front(); for (int v : adj[u]){ if (dis[v] == inf){ dis[v] = dis[u] + 1; d.push(v); } if (dis[v] == dis[u] + 1) dp[v] += dp[u]; } } vis[rt] = 1; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int a,b; m; m--){ cin >> a >> b; adj[a].push_back(b), adj[b].push_back(a); } cin >> k; for (int a,b; k; k--){ cin >> a >> b; bfs(a, dis[a], dp[a]), bfs(b, dis[b], dp[b]); for (int i=0; i<n; i++) if (dis[a][i] + dis[b][i] == dis[a][b]) val[i] += double(dp[a][i]*dp[b][i])/dp[a][b]; } for (int i=1; i<n; i++) if (val[i] > val[k]) k = i; cout << k << "\n"; 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...