校园通行查询

知识点与目标

多源最短路径、Floyd。前置：无向图、二维数组、三重循环、long long。

解题思路

询问很多，而建筑最多300栋，先求所有建筑对之间的最短距离。初始化 d[i][i]=0，其余为 INF；每条双向步道更新两个方向，重边取最小值。依次枚举中间点 k，再枚举 i,j，用 d[i][k]+d[k][j] 更新 d[i][j]。预处理后，每次询问直接查表，不可达输出-1。

正确性说明

令 D_k(i,j) 表示内部顶点只允许取自1到k时的最短距离。初始化对应不允许内部顶点的路线。最优路线若不经过k，则为 D_(k-1)(i,j)；若经过k，则拆成 i到k 和 k到j 两段，取两段最优距离之和。非负边权下可以去掉环而不增加代价，所以只需考虑上述拆分。转移取两者最小，由归纳得第n轮后为全部最短距离。零权环不影响结论，对角线为0保证原地更新有效。

易错点

k 必须在最外层；步道是双向的；读入重边应取最小值，不能覆盖；对角线初始化为0；INF不能参与未经检查的加法；同点查询输出0；每个答案单独一行。long long避免长距离溢出，最大合法最短距离不超过(n-1)×10^9。

复杂度

时间 O(n^3+m+q)，空间 O(n^2)。

难度依据

4·普及，geekpi-9-v2。需要根据最多300个顶点和10万次询问识别预处理需求，理解按允许中间点递增的状态转移与循环顺序；无需额外状态扩展或多算法组合。

C++17 参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,m,q;if(!(cin>>n>>m>>q))return 0;
    const long long INF=(1LL<<62);
    vector<vector<long long>> d(n+1,vector<long long>(n+1,INF));
    for(int i=1;i<=n;i++)d[i][i]=0;
    for(int i=0,u,v;i<m;i++){long long w;cin>>u>>v>>w;d[u][v]=d[v][u]=min(d[u][v],w);}
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)if(d[i][k]!=INF)
        for(int j=1;j<=n;j++)if(d[k][j]!=INF)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    while(q--){int a,b;cin>>a>>b;cout<<(d[a][b]==INF?-1:d[a][b])<<'\n';}
}