题目描述

现有 i 个哨所，他们之间有 k 条通信相连，每条通信耗时 k 天，若从哨所 1 出发，求通信经过全哨所的最短时间
样例如下
输入
4 4
1 2 4
2 3 7
2 4 1
3 4 6
输出
11

问题描述

在做本题时，我使用Floyed算法来求最小路径，代码如下

#include
using namespace std;

int n,m,x,y,t,ans,f[110][110];

int main(){

// 初始化 
for(int i=0;i<101;i++){
    for(int j=0;j<101;j++){
        f[i][j]=100100;
    }
}

// 输入 
cin >> n >> m;
for(int i=1;i<=m;i++){
    // 起点，终点，权值 
    cin >> x >> y >> t;
    f[x][y]= t;
    f[y][x] = t;
}

// 自己到自己的时间为0 
for(int i=1;i<=n;i++){
    f[i][i]=0;
}

// Floyed算法 
for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            // 直接到达或间接到达 
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
        }
    }
}

for(int i=1;i<=n;i++){
    ans = max(ans,f[1][i]);
}
// 若无法到达当前结点 
if(ans>=100100){
    cout << -1;
}else{
    cout << ans << endl;
}

}

在使用当前代码测试以下样例
4 4
1 2 3
2 4 1
1 3 4
3 4 10
期望输出：8
实际输出：4

经过debug，发现是在
// Floyed算法
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
// 直接到达或间接到达
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}

出的问题，此处f[1][4]是3，即f[1][2] + f[2][4] 并没有经过点3，我改如何修改Floyed核心代码以解答呢？

样例错了吧
从1到2，路径1-2，时间3
从1到3，路径1-3，时间4
从1到4，路径1-2-4，时间4
还是说我们理解错了题意？