【正经题解】农场移动

通过邻接矩阵 $a$ 表示农田之间的单向道路，其中 $a$ [ $i$ ][ $j$ ] 表示从 $i$ 到 $j$ 的距离或消耗体力。
计算任意两点之间的最短路径。
输出从 $s$ 到 $t$ 的最短路径所需的最少体力。

#include<bits/stdc++.h>

using namespace std;

int n, m, s, t, a[105][105];

int main() {
    cin >> n >> m >> s >> t;
    memset(a, 0x3f, sizeof(a));

    // 处理输入，构建邻接矩阵
    while(m--){
        int x, y, z;
        cin >> x >> y >> z;
        a[x][y] = z;
    }

    // 使用Floyd-Warshall算法计算任意两点之间的最短路径
    for(int i = 1; i <= n; i++) 
        a[i][i] = 0;

    for(int k = 1; k <= n; k++){ 
        for(int i = 1; i <= n; i++){ 			
            for(int j = 1; j <= n; j++){ 
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }

    // 输出从s到t的最短路径所需的最少体力
    cout << a[s][t];

    return 0;
}