Submission #537348

#TimeUsernameProblemLanguageResultExecution timeMemory
537348ac2huHotspot (NOI17_hotspot)C++14
100 / 100
1014 ms980 KiB
#include <bits/stdc++.h> #ifdef DEBUG #include "../templates/debug.h" #else #define deb(x...) #endif using namespace std; #define ll long long #define ld double const int N = 5001; int n,m,k; vector<int> adj[N]; int d1[N], d2[N] ,p1[N], p2[N]; ld e[N]; signed main() { iostream::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); cout << setprecision(10); cin >> n >> m; for(int _ = 0;_<m;_++){ int a,b;cin >> a >> b; // a--;b--; adj[a].push_back(b); adj[b].push_back(a); } cin >> k; for(int _ = 0;_<k;_++){ int s,t;cin >> s >> t; for(int i = 0;i<n;i++){ d1[i] = 1e9; d2[i] = 1e9; p1[i] = 0; p2[i] = 0; } list<int> q; d1[s] = 0; p1[s] = 1; q.push_back(s); while(!q.empty()){ int x = q.front(); q.pop_front(); // cout << x << "--> : "; for(int e : adj[x]){ if(d1[e] > d1[x]){ p1[e] += p1[x]; } if(d1[e] > d1[x] + 1){ d1[e] = d1[x] + 1; // cout << e << " "; q.push_back(e); } } // cout << "\n"; } // cout << "\n"; // p2 shortest paths to t d2[t] = 0; p2[t] = 1; q.push_back(t); while(!q.empty()){ int x = q.front(); q.pop_front(); for(int e : adj[x]){ if(d2[e] > d2[x]) p2[e] += p2[x]; if(d2[e] > d2[x] + 1){ d2[e] = d2[x] + 1; q.push_back(e); } } } assert(p1[t] == p2[s]); ll total = p1[t]; // assert(p1[t] == p2[s]); for(int i = 0;i<n;i++){ ll paths = p1[i]*p2[i]; if(d1[i] + d2[i] == d1[t] && d1[t] < 1e8) e[i] += ((ld)paths/total); } // cout << s << " " << t << "\n"; // cout << "distance from " << s << " to i: \n"; // for(int i = 0;i<n;i++) // cout << d1[i] << " "; // cout << "\n"; // cout << "distance from " << t << " to i: \n"; // for(int i = 0;i<n;i++) // cout << d2[i] << " "; // cout << "\n"; // cout << "paths from " << s << " to i: \n"; // for(int i = 0;i<n;i++) // cout << p1[i] << " "; // cout << "\n"; // cout << "paths from " << t << " to i: \n"; // for(int i = 0;i<n;i++) // cout << p2[i] << " "; // cout << "\n"; // cout << "------------\n"; } // for(int i = 0;i<n;i++) // cout << e[i] << " "; // cout << "\n"; cout << max_element(e, e + n) - e << "\n"; }
#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...