Submission #587494

#	Time	Username	Problem	Language	Result	Execution time	Memory
587494		gg123_pe	Hotspot (NOI17_hotspot)	C++14	100 / 100	1615 ms	338000 KiB

hotspot

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

#define f(i,a,b) for(ll i = a; i < b; i++)
#define fa(i,a,b) for(ll i = a; i >= b; i--)

const int N = 5005; 
const int inf = 2e9; 


int a[N], b[N], n, m, d[N][N]; 
ld c[N][N]; 
vector <int> adj[N];

void dfs(int u){
    f(i,1,n+1) d[u][i] = inf; 

    d[u][u] = 0; 
    queue <int> q; 
    q.push(u); 

    c[u][u] = 1; 

    while(!q.empty()){
        int v = q.front(); q.pop();

        for(int f: adj[v]){
            if(d[u][f] > d[u][v] + 1){
                d[u][f] = d[u][v] + 1; 
                c[u][f] = c[u][v];
                q.push(f);
            }
            else if(d[u][f] == d[u][v] + 1) c[u][f] += c[u][v]; 
        }
    }
}
int main(){
    cin >> n >> m; 

    f(i,0,m){
        int x, y; cin >> x >> y; 
        x++, y++; 
        adj[x].push_back(y), adj[y].push_back(x);
    }

    f(i,1,n+1) dfs(i); 

    int k, ans = 0; cin >> k; 
    f(i,1,k+1) {
        cin >> a[i] >> b[i]; 
        a[i]++, b[i]++; 
    }

    ld ANS = 0; 

    f(i,1,n+1){
        ld res = 0; 

        f(j,1,k+1){
            if(d[a[j]][b[j]] == d[a[j]][i] + d[i][b[j]]){
                res += (c[a[j]][i]*c[i][b[j]]) / c[a[j]][b[j]];
            }
        }
        if(res > ANS){
            ANS = res; 
            ans = i; 
        }
    }
    cout << --ans << "\n";
    return 0; 
}

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