# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
426619 | TLP39 | Hotspot (NOI17_hotspot) | C++14 | 1076 ms | 1180 KiB |
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>
using namespace std;
typedef pair<int,pair<int,int>> pii;
int n,m,k;
vector<int> adj[5003];
int shortest_path[2][5003];
int num_shortest_path[2][5003];
bool marked[2][5003];
double final[5003];
void bfs(int a,int pos)
{
for(int i=0;i<n;i++)
{
marked[pos][i]=false;
shortest_path[pos][i]=1000000;
num_shortest_path[pos][i]=0;
}
queue<int> q;
int temp;
q.push(a);
marked[pos][a]=true;
shortest_path[pos][a]=0;
num_shortest_path[pos][a]=1;
while(!q.empty())
{
temp=q.front();
q.pop();
for(int i=0;i<adj[temp].size();i++)
{
if(shortest_path[pos][adj[temp][i]]<=shortest_path[pos][temp]) continue;
if(!marked[pos][adj[temp][i]])
{
marked[pos][adj[temp][i]]=true;
shortest_path[pos][adj[temp][i]]=shortest_path[pos][temp]+1;
q.push(adj[temp][i]);
}
num_shortest_path[pos][adj[temp][i]]+=num_shortest_path[pos][temp];
}
}
}
int main()
{
scanf("%d %d",&n,&m);
int u,v;
for(int i=0;i<m;i++)
{
scanf("%d %d",&u,&v);
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=0;i<n;i++) final[i]=(double)0;
scanf("%d",&k);
while(k--)
{
scanf("%d %d",&u,&v);
bfs(u,0);
bfs(v,1);
for(int i=0;i<n;i++)
{
if(shortest_path[0][v]!=shortest_path[0][i]+shortest_path[1][i]) continue;
final[i]+=((double)(num_shortest_path[0][i]*num_shortest_path[1][i]))/((double)(num_shortest_path[0][v]));
}
}
double maxi=(double)(-1);
int posi=-1;
for(int i=0;i<n;i++)
{
if(final[i]>maxi)
{
maxi=final[i];
posi=i;
}
}
printf("%d",posi);
}
Compilation message (stderr)
# | 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... |