Submission #1194111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194111		_rain_	Hotspot (NOI17_hotspot)	C++20	100 / 100	911 ms	216036 KiB

hotspot

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)5000;
const int M=40000;
vector<int>ke[N+2];
LL d[N+2][N+2]={};
int dd[N+2][N+2]={},u[M+2],v[M+2],a[M+2],b[M+2];
int n,m,k;

void djisktra(int source){
	queue<int>q;
	for(int i=1;i<=n;++i) dd[source][i]=-1;
	dd[source][source]=0;
	d[source][source]=1;
	q.push(source);
	while (q.size()){
		int u=q.front(); q.pop();
		for(auto&v:ke[u]){
			if (dd[source][v]==-1){
				d[source][v]=d[source][u];
				dd[source][v]=dd[source][u]+1;
				q.push(v);
			}
			else if (dd[source][v]==dd[source][u]+1) d[source][v]+=d[source][u];
		}
	}
	return;
}

void add_canh(int u,int v){
	ke[u].push_back(v),
	ke[v].push_back(u);
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
//	freopen("main.inp","r",stdin);
	
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>u[i]>>v[i];
		++u[i],++v[i];
		add_canh(u[i],v[i]);
	}
	for(int i=1;i<=n;++i) djisktra(i);
	cin>>k;
	for(int i=1;i<=k;++i) {
		cin>>a[i]>>b[i];
		++a[i],++b[i];
	}
	double cur=0;
	int ans=-1;
	for(int i=1;i<=n;++i){
		double x=0;
		for(int j=1;j<=k;++j){
			int s2=d[a[j]][b[j]];
			int s1=0;
			if (dd[a[j]][i]+dd[b[j]][i]==dd[a[j]][b[j]]) s1=d[a[j]][i]*d[b[j]][i];
			if (s2!=0) x+=(double)s1/s2;
		}
		if (cur<x){
			cur=x;
			ans=i;
		}
	}
	cout<<ans-1;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 18 / 18
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36