// 1 / 5
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>
/*
+ array limit ???
+ special case ??? n = 1?
+ time limit ???
*/
using namespace std;
const int INF = 1e18 + 7;
const int maxn = 5e3 + 7;
vector <int> g[5005];
int n , k , m , f[5005][5005] , ways[5005][5005];
pii query[maxn];
void bfs(int st)
{
for(int i = 1; i <= n; i++) f[st][i] = INF;
f[st][st] = 0;
ways[st][st] = 1;
queue <int> Q;
Q.push(st);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int v: g[u])
{
if(f[st][v] > f[st][u] + 1)
{
f[st][v] = f[st][u] + 1;
ways[st][v] = ways[st][u];
Q.push(v);
}
else if(f[st][v] == f[st][u] + 1)
{
ways[st][v] += ways[st][u];
}
}
}
}
pair <double , int> ans = {-1 , -1};
void solve()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int u , v; cin >> u >> v;
u++, v++;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++) {bfs(i);}
cin >> k;
for(int i = 1; i <= k; i++)
{
cin >> query[i].fi >> query[i].se;
}
for(int u = 1; u <= n; u++)
{
int total = 0 , sum = 0;
bool check = 1;
for(int i = 1; i <= k; i++)
{
if(f[query[i].fi][u] + f[u][query[i].se] > f[query[i].fi][query[i].se])
{
check = 0; break;
}
sum += ways[query[i].fi][u] * ways[query[i].se][u];
total += ways[query[i].fi][query[i].se];
}
if(check)
{
ans = max(ans , {(double)(1.0 * sum / total) , u});
}
}
cout << ans.se - 1 << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
# | 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... |