Submission #619913

#TimeUsernameProblemLanguageResultExecution timeMemory
619913PoonYaPatHotspot (NOI17_hotspot)C++14
100 / 100
1553 ms338468 KiB
#include <bits/stdc++.h> using namespace std; int n,m,k,d[5001][5001],ans_node,x[2001],y[2001]; vector<int> adj[5001]; queue<int> q; long double ans,cnt[5001][5001]; void bfs(int x) { memset(d[x],0x3f,sizeof(d[x])); q.push(x); d[x][x]=0; cnt[x][x]=1; while (!q.empty()) { int a=q.front(); q.pop(); for (auto s : adj[a]) { if (d[x][s]>d[x][a]+1) { d[x][s]=d[x][a]+1; cnt[x][s]+=cnt[x][a]; q.push(s); } else if (d[x][s]==d[x][a]+1) cnt[x][s]+=cnt[x][a]; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for (int i=0; i<m; ++i) { int a,b; cin>>a>>b; adj[a].push_back(b); adj[b].push_back(a); } cin>>k; for (int i=0; i<k; ++i) cin>>x[i]>>y[i]; for (int i=0; i<n; ++i) bfs(i); for (int i=0; i<n; ++i) { long double sum=0; for (int j=0; j<k; ++j) { if (d[x[j]][i]+d[i][y[j]]==d[x[j]][y[j]]) { sum+=(cnt[x[j]][i]*cnt[i][y[j]])/cnt[x[j]][y[j]]; } } if (sum>ans) ans_node=i,ans=sum; } cout<<ans_node; }
#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...