제출 #1170922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170922		nguyenkhangninh99	Hotspot (NOI17_hotspot)	C++20	100 / 100	820 ms	154624 KiB

hotspot

#include <bits/stdc++.h>
 
using namespace std;
 
 
const int maxn = 5e3 + 5;
 
int d[maxn][maxn], a[maxn], b[maxn];

int cnt[maxn][maxn];
double s[maxn]; 
 
vector<int> adj[maxn];
 int n, m; 
void dijk(int id){
    queue<int> q;
 
    for(int i = 1; i <= n; i++) d[id][i] = 1e9;
 
    q.push(id);
    d[id][id] = 0;
    cnt[id][id] = 1;
 
    while(q.size()){
        int u = q.front();
        q.pop();
 
        for(int v: adj[u]){ 
            if(d[id][v] > d[id][u] + 1){
                cnt[id][v] = cnt[id][u];
                d[id][v] = d[id][u] + 1;
                q.push(v);
            }
            else if(d[id][v] == d[id][u] + 1) cnt[id][v] = cnt[id][v] + cnt[id][u];
        }
    }
 
}

void solve(){
    cin >> n >> m;
 
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
		u++;
		v++;
        adj[u].push_back(v);
		adj[v].push_back(u);
    }
	
	for(int i = 1; i <= n; i++) dijk(i);

	int k; cin >> k;

	for(int i = 1; i <= k; i++){
        cin >> a[i] >> b[i];
        a[i]++; b[i]++;
    }
	
	double mx = -2e9, ans;
	for(int i = 1; i <= n; i++){
        s[i] = 0;
		for(int j = 1; j <= k; j++){
			if(d[a[j]][i] + d[i][b[j]] == d[a[j]][b[j]]){
                double s1 = cnt[a[j]][i], s2 = cnt[i][b[j]], s3 = cnt[a[j]][b[j]];
				s[i] = s[i] + (s1 * s2) / s3;
			}
		}
		if(s[i] > mx){
			mx = s[i];
			ans = i;
		}

	}

	cout << ans - 1;

}
 
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    

    solve();
}

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