제출 #1105345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105345		minhvule	Hotspot (NOI17_hotspot)	C++17	38 / 100	60 ms	608 KiB

hotspot

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define freo(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
#define FOR(i, a, b) for(int i=(a),_b = (b); i<=_b; i++)
#define FORD(i, a, b) for(int i=(a),_b = (b); i>=_b; i--)
#define bit(x, i) ((x >> i) & 1)
#define oo 1e18
#define pii pair<int, int>
#define debug cout<<"VUDEPTRAI\n";
using namespace std;
// mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
// ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int N = 5e3 + 5;
int n, m, k, cnt[N], from[N];
vector<int> g[N];
void dijkstra(int u, int v){
    vector<int> d(N, INT_MAX);
    priority_queue<pii> pq;
    pq.push({0, u});
    while(!pq.empty()){
        pii top = pq.top();
        pq.pop();
        int u = top.second;
        if(top.first > d[u]) continue;
        for(int v:g[u])
            if(d[v] > d[u] + 1){
                d[v] = d[u] + 1;
                from[v] = u;
                pq.push({d[v], v});
            }
    }
    while(v != u){
        cnt[v] ++;
        v = from[v];
    }
    cnt[u] ++;
}
void solve(){
    cin>>n>>m;
    FOR(i, 1, m){
        int u, v; cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    cin>>k;
    FOR(i, 1, k){
        int a, b; cin>>a>>b;
        dijkstra(a, b);
    }
    int ans = -1, tmp = INT_MIN;
    FOR(i, 1, n)
        if(cnt[i] > tmp){
            tmp = cnt[i];
            ans = i;
        }
    cout<<ans;
}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    // freo("");
    solve();
    // cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}
/*
 


*/

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