AcWing 345. 牛站题解（floyd性质与倍增）

AcWing 345. 牛站
解题思路：本题所采用的floyd算法与传统用于求解最短路径的floyd算法存在本质区别，尽管两者均涉及三重循环结构，但此处d[k][i][j]所表示的含义是节点i到节点j经过k条边时的最短路径长度。在明确这一定义之后，进一步推导出d[a+b][i][j] = min(d[a+b][i][j], d[a][i][k] + d[b][k][j])。由于d[a][i][k]与d[b][k][j]之间互不干扰，因此可以联想到利用快速幂的思想来计算最短路径。

大老远题解

    #include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 210;
    
    map<int, int>mp;
    int n, m, S, E, k;
    int