人类群星闪耀时

Nostopathy · 2026-06-22 20:18:59 · 题解

先贴个头图。

由于 n \le 10^4，暴力求最短路是不行的，考虑乱搞充分发扬人类智慧。

只能确定这些被遗忘的最快速行船路线的所需时间的值至少严格大于 \sqrt{n}。

由于图上边权全为 1，这代表着路径经过至少 \sqrt{n} 个点。那么，随机选点落在路径上的概率就大于等于 \frac{\sqrt{n}}{n}=\frac{1}{\sqrt{n}}。

一旦出现落在路径上的点，它到两端点 s,t 的距离之和就是 s 到 t 最短路了。故我们考虑随机取 x 个点，计算其中至少有一个在路径上的概率。

选一个点不在路径上的概率小于等于 1-\frac{1}{\sqrt{n}}，故所选 x 个点都不在的概率小于等于 (1-\frac{1}{\sqrt{n}})^x。用 1 减去这部分概率，得到的就是至少有一个点在路径上的概率，大于等于 1-(1-\frac{1}{\sqrt{n}})^x。

故我们在该问题上完全正确的概率大于等于 (1-(1-\frac{1}{\sqrt{n}})^x)^q，由于 1-\frac{1}{\sqrt{n}}<1，x 越大越好。综合考虑一下时空限制，x 取 2000 较为合适。

故随机摇 2000 个点，求它们开始的最短路，对每组询问，在这些点里取到 s,t 最短路之和最小的值回答即可。

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

const int N = 10001, M = 2001;
const LL inf = 1e15;

int n, m, questions, id[M];
bool vis[N];
LL dis[M][N];
vector<int> G[N];

void shortestPath(int r, int s){
    for(int i = 1; i <= n; ++ i) vis[i] = 0, dis[r][i] = inf;
    dis[r][s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v : G[u])
            if(dis[r][v] == inf){
                dis[r][v] = dis[r][u] + 1;
                q.push(v);
            }
    }
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> questions;
    for(int i = 1, u, v; i <= m; ++ i){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int t = min(n, 2000);
    for(int i = 1; i <= t; ++ i) id[i] = rand() % n + 1;
    for(int i = 1; i <= t; ++ i) shortestPath(i, id[i]);
    while(questions --){
        int s, to;
        cin >> s >> to;
        LL ans = inf;
        for(int i = 1; i <= t; ++ i) ans = min(ans, dis[i][s] + dis[i][to]);
        cout << ans << " ";
    }

    return 0;
}