算法日记19：SC71多元最短路(Floyd)

一、题目：

二、题解： 1、我们一眼就可以看出这是一道多源最短路的题目，因此直接套用Floyd模板即可 2、Floyd原理解析 2.1：假设现在我们有这样一个图，要求我们求任意两个顶点的距离

2.2：对于这个样例，我们使用Floyd来做的步骤如下：（顺序不能改变！！）

其中，我们并不关心两个点之间是怎么连接的，仅仅只是枚举所有情况，查看是否有其他情况使得两个点之间的路径更小 2.3：也就是意味着我们要使用 O O O(n3)的时间复杂度，因此点/边的数量级一般<1e3 我们并不证明公式的正确性，背下模板即可 三、代码解析如下： 3.1:代码分块解析

它的核心思想是通过多次迭代来更新路径，逐步得到图中任意两点的最短距离。下面是详细分块解释：

1. 常量与类型定义 typedef long long ll; const int N=307; ll dis[N][N]; //表示从i-->j的距离 typedef long long ll;：定义 ll 为 long long 类型的别名，简化代码书写。const int N=307;：定义常量 N 为 307，表示最多有 307 个节点。这个值是预设的最大节点数，通常会根据问题要求进行调整。ll dis[N][N];：定义一个二维数组 dis，用来存储节点间的最短距离，dis[i][j] 表示从节点 i 到节点 j 的最短距离。 2. solve() 函数 void solve() { ll n,m,q;cin>>n>>m>>q; memset(dis,0x3f,sizeof(dis)); ll n,m,q;cin>>n>>m>>q;：输入图的节点数 n，边数 m，以及询问次数 q。memset(dis,0x3f,sizeof(dis));：初始化 dis 数组，填充为一个非常大的值（0x3f3f3f3f），表示初始状态下所有节点之间的距离都是无穷大，除非通过边连接。 0x3f3f3f3f 代表一个足够大的值，用于模拟“无穷大”。在后面的计算中，任何距离小于这个值的都会被替代。 3. 输入边的信息并更新距离 for(int i=1;i<=m;i++) { ll ui,vi,wi;cin>>ui>>vi>>wi; dis[ui][vi]=min(dis[ui][vi],wi); //对重边/自环的处理 } for(int i=1;i<=m;i++)：循环处理每一条边。cin>>ui>>vi>>wi;：输入边的信息，ui 和 vi 是节点，wi 是边的权重。dis[ui][vi]=min(dis[ui][vi],wi);：更新 dis 数组中 dis[ui][vi] 的值，如果已经有路径存在，取最小值。这样可以处理重边或自环的情况，即如果两点之间有多个边，则选择权重最小的那个边。 4. 初始化对角线 for(int i=1;i<=n;i++) dis[i][i]=0; 这里将每个节点到自身的距离设置为 0，因为任何节点到自身的最短路径显然是 0。 5. Floyd算法核心 for(int k=1;k<=n;k++)//中转点 for(int i=1;i<=n;i++) //起始点 for(int j=1;j<=n;j++) //指向点 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 这部分实现了 Floyd-Warshall 算法的核心逻辑。 k 是中转点，表示通过 k 来更新其他节点之间的最短路径。外层的 i 表示起始点，内层的 j 表示目标点。dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); 这个公式的含义是，如果从 i 到 j 的路径通过 k 节点更短，则更新 dis[i][j] 的值。通过三重循环对每一对节点 (i, j) 进行更新，遍历所有可能的中转点 k。 6. 处理询问 while(q--) //q次询问 { ll ui,vi;cin>>ui>>vi; if(dis[ui][vi]>=4e18) cout<<-1<<'\n'; else cout<<dis[ui][vi]<<'\n'; } } while(q--)：处理每次询问，询问次数为 q。cin>>ui>>vi;：输入一对节点 ui 和 vi。if(dis[ui][vi]>=4e18)：如果 dis[ui][vi] 的值大于等于一个非常大的值 4e18（即无穷大），说明这两点之间不可达，输出 -1。else cout<<dis[ui][vi]<<'\n';：否则，输出 dis[ui][vi]，即节点 ui 到节点 vi 的最短距离。 3.2:完整代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=307; ll dis[N][N]; //表示从i-->j的距离 void solve() { ll n,m,q;cin>>n>>m>>q; memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=m;i++) { ll ui,vi,wi;cin>>ui>>vi>>wi; dis[ui][vi]=min(dis[ui][vi],wi); //对重边/自环的处理 } //初始化 for(int i=1;i<=n;i++) dis[i][i]=0; for(int k=1;k<=n;k++)//中转点 for(int i=1;i<=n;i++) //起始点 for(int j=1;j<=n;j++) //指向点 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); while(q--) //q次询问 { ll ui,vi;cin>>ui>>vi; if(dis[ui][vi]>=4e18) cout<<-1<<'\n'; else cout<<dis[ui][vi]<<'\n'; } } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int _=1; while(_--)solve(); return 0; }