前言
这题纯纯 floyd 模板题。给不熟悉 floyd 的孩子们科普一下：
一、算法背景
在图论中，全源最短路径问题（All-Pairs Shortest Paths）需要找出任意两点之间的最短路径。Floyd算法（Floyd-Warshall算法）是一种经典、简单且高效的解决方案，适用于边权为正或负（但不能有负权环）的稠密图。
二、适用场景
有向图或无向图。
边权可以为负数（但不能存在负权回路）。
需要计算所有点对之间的最短距离。
三、核心思想
Floyd算法的核心是动态规划：通过枚举每一个中转点 kkk ，检查是否能优化 iii 到 jjj 的路径。其状态转移方程为：
dpi,j=min(dpi,k+dpj,k,dpi,j)dp_{i, j} = min(dp_{i, k} + dp_{j, k}, dp{i, j}) dpi,j =min(dpi,k +dpj,k ,dpi,j)
状态转移方程解释：
若从 iii 直接到 jjj 的路径比从 kkk 中转的路径更长，就更新路径。
四、FLOYD代码模板（注意不是本题AC代码）
本题思路
首先初始化每条边为 INF（因为题目不保证每两个节点都有连边），随后再根据给的边和边权建边，随后 floyd 一下，最后输出询问答案即可。
AC代码
最后祝大家都能 rp++。
