제출 #1205209

#제출 시각아이디문제언어결과실행 시간메모리
1205209loomHotspot (NOI17_hotspot)C++20
100 / 100
1022 ms245500 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++){ queue<int> q; auto &dist = d[i]; auto &cnt = c[i]; vector<int> vis(n, 0); q.push(i); dist[i] = 0; cnt[i] = 1; vis[i] = 1; while(!q.empty()){ int v = q.front(); q.pop(); for(int ch : g[v]){ if(!vis[ch]){ vis[ch] = 1; dist[ch] = dist[v]+1; cnt[ch] = cnt[v]; q.push(ch); } else if(dist[v]+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 += (ld)(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...