This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else
#define deb(x...)
#endif
using namespace std;
#define ll long long
#define ld long 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |