제출 #1239539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239539		eirinayukari	Hotspot (NOI17_hotspot)	C++20	100 / 100	933 ms	1040 KiB

hotspot

// XD XD
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define el cout << "\n";

using namespace std;
using ll = long long;

const int MAXN = 5000 + 7;
const int MAXK = 2000 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LLINF = 1e18 + 7;

template <typename T>
bool ckmin(T& a, T b) {
    return a > b ? a = b, true : false;
}

template <typename T>
bool ckmax(T& a, T b) {
    return a < b ? a = b, true : false;
}

int n, m, k;
int a[MAXK], b[MAXK];
int bdist[MAXK], bways[MAXK];
int dist[MAXN], ways[MAXN];
vector<int> adj[MAXN];  
queue<int> q;

void bfs(int u) {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        ways[i] = 0;
    }
    q = {};

    dist[u] = 0;
    ways[u] = 1;
    q.push(u);

    while (q.size()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                ways[v] = ways[u];
                q.push(v);
            } else if (dist[v] == dist[u] + 1) {
                ways[v] += ways[u];
            }
        }
    }
}

void solve(int id) {
    // cout << "Case " << id << ": ";
    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);
    }

    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> a[i] >> b[i];
        a[i]++;
        b[i]++;
    }

    for (int i = 1; i <= k; i++) {
        bfs(a[i]);
        bdist[i] = dist[b[i]];
        bways[i] = ways[b[i]];
    }

    double expv = -INF;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        double expi = 0;
        bfs(i);
        for (int j = 1; j <= k; j++) {
            int tot = dist[a[j]] + dist[b[j]];
            if (tot == bdist[j]) {
                expi += 1.0 * (ways[a[j]] * ways[b[j]]) / bways[j];
            }
        }

        if (ckmax(expv, expi)) {
            ans = i;
        }
    }
    cout << ans - 1 << "\n"; 
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    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